On Certifying the Unreachable

Control engineering spends a lot of time asking a very optimistic question:

Can I move this system wherever I want?

This is a beautiful question that hides behind a suspicious state (I swear I did not intend this pun to be). In real engineering systems, especially large infrastructure networks, the more urgent question is often the opposite:

Can I quickly prove that I cannot move this system somewhere?

That is the idea behind a recent paper I wrote with my students Kazma and Abdallah. The paper is technical, but the core idea is simple: if a desired maneuver is impossible, optimization already knows how to give you a witness of that impossibility. That witness is an infeasibility certificate. In this control setting, that certificate is not just a computational receipt saying no! It actually control-theoretic information by pointing back to the well-known PBH modes that make the system uncontrollable.

Read the paper: Revisiting the PBH Test: Fast Uncontrollability Certificates via Krylov Methods

This essay is my attempt to tell that story. The reader only needs basic linear algebra and some systems control background.

State-Space Models

A dynamic system model, around an operating point, can be written as a linear discrete-time model:

$$ x_{k+1} = A x_k + B u_k . \tag{1} $$

At time $k$, vector $x_k$ is the state. This state vector might store voltages in a power grid, water flows in pipes, vehicle densities on road links, or temperatures in rooms. You see, getting to where you wanna get to is a metaphorical concept that goes beyond velocities and displacements.

Anyway, vector $u_k$ is what I can directly change (valve settings, generator inputs, ramp metering decisions, heater power, and so on). Matrix $A$ tells me how the system evolves on its own, basically its parameters and underlying physics (sigma-f-equals-ma, and its many variants in mass, energy, and momentum conservation). Matrix $B$ tells me where the input actually enters, i.e., the geography of the inputs.

A system may have thousands of states, but only a handful of actuators or control inputs. A traffic network might have sensors everywhere but controllable signals only at a few intersections. A water network might have hundreds of pipes but pumps and valves in only a few places. Some water networks are gravity-controlled, meaning no pump or valve controls anything, just Newton and his apple. So even if the model is linear, the question of what the input can actually influence is not obvious. After $N$ steps, expanding the recursion in (1) gives $$ x_N = A^N x_0 + A^{N-1}B u_0 + A^{N-2}B u_1 + \cdots + B u_{N-1}. \tag{2} $$ Move the natural evolution $A^N x_0$ to the left and define the desired displacement, which I call the maneuver:

$$ \Delta x = x_N - A^N x_0. \tag{3} $$

Then the reachability question becomes

$$ C_N u = \Delta x, \qquad C_N = [B, AB, A^2B, \ldots, A^{N-1}B]. \tag{4} $$

Matrix $C_N$ in (4) is the finite-horizon controllability matrix. Its columns are all the directions that can be produced by pushing on the system now, then letting the dynamics carry that push forward. If $\Delta x$ lives in the range of $C_N$, meaning the span of the columns of $C_N$, then some input sequence gets you there…where you wanna be is feasible. If $\Delta x$ does not live in that range, then no input sequence can do it. No amount of clever linear algebra can get you there.

The Classical Controllability Question

The system is controllable if, for a long enough horizon, $C_N$ spans the whole state space. In an $n$-state system, this usually appears as $$ \operatorname{rank}[B, AB, \ldots, A^{n-1}B] = n. \tag{5} $$

That test is old (predates everyone reading this blog), foundational, and still extremely useful. There is also the PBH test, named after Popov, Belevitch, and Hautus. It says that the pair $(A,B)$ is controllable if and only if

$$ \operatorname{rank}[\lambda I - A \quad B] = n \tag{6} $$

for every eigenvalue $\lambda$ of $A$. Equivalently, the system is uncontrollable if there exists a nonzero left eigenvector $w$ such that

$$ w^T A = \lambda w^T, \qquad w^T B = 0. \tag{7} $$

The condition $w^T B = 0$ in (7) is the cornerstone of this theory. It says there is a mode of the system that the input cannot see. The dynamics may have a direction that evolves perfectly well under $A$, but the input matrix $B$ is orthogonal to it. You can push all you want. That mode refuses to hear you. In my opinion, this is one of the simplest and prettiest facts in linear systems theory. It turns the geometric question of what can inputs reach? into the modal question which eigenvectors are invisible to the inputs?

The Literature Likes Controllability, so the Anti-Controllability Man Is Here

A large amount of control and network science literature revolves around controllability. I am here to be the Anti-Christ of controllability. Let me explain what motivates this apprehension or gentle disdain.

Controllability is the gateway property. Before designing a controller, placing actuators, or optimizing an input, you want to know what is possible. There are rank tests, PBH tests, Gramian metrics, minimum-energy metrics, actuator placement problems, network controllability papers, structural controllability papers, empirical Gramian papers, and many other variants. Some of this literature asks binary questions: is the system controllable or not? Some asks quantitative questions: how hard is it to control? How much energy is needed? Which states are hard to move? Which actuator should I add? But there is a quieter problem that deserves more attention:

How do I rapidly certify uncontrollability for a specific target or maneuver $\Delta x$, especially when the model is changing?

A power grid, transportation network, or water distribution network may be linearized repeatedly around different operating points, every few minutes or so. Matrix $A$ changes and sometimes $B$ changes too. A full eigendecomposition or a full controllability matrix may be too expensive or too fragile to compute every time. And often I do not need the entire controllability story. I only need to know whether one proposed maneuver is impossible. Here are some practical examples.

• Can these ramp meters move congestion away from this corridor in the next few minutes?
• Can these valves produce a desired pressure change at a vulnerable district?
• Can these generators influence a weak oscillatory mode after a contingency?
• Can this local HVAC controller get the room to a desired temperature within a few minutes?

If the answer is no, it is useful to have a fast certificate. Not a vague warning and not a numerical shrug. A certificate.

A Physical Example: Two Tanks and One Pump

Imagine two water tanks connected by a pipe. The state is the pair of water levels,

$$ h = \begin{bmatrix} h_1 \\ h_2 \end{bmatrix}. \tag{8} $$

There is one pump, and it injects water only into the first tank. The second tank can only be influenced through the pipe connecting the two tanks. A simple linearized model around an operating point is

$$ \dot h = A h + B u, \quad A = \begin{bmatrix} -(\alpha+\kappa) & \kappa \\ \kappa & -(\gamma+\kappa) \end{bmatrix}, \quad B = \begin{bmatrix} 1 \\ 0 \end{bmatrix}. \tag{9} $$

Here $\alpha$ and $\gamma$ represent leakage or outflow effects, while $\kappa$ is the hydraulic parameter of the pipe between the tanks. If the pipe is open, $\kappa > 0$. If an isolation valve is closed, or if the local linearization sees no flow sensitivity through that connection, then $\kappa = 0$. The controllability matrix for this two-state system is

$$ [B \quad AB] = \begin{bmatrix} 1 & -(\alpha+\kappa) \\ 0 & \kappa \end{bmatrix}. \tag{10} $$

The rank of the matrix in (10) is $2$ exactly when $\kappa \neq 0$:

$$ \det [B \quad AB] = \kappa. \tag{11} $$

So the entire controllability story is hiding in one physical quantity: the pipe parameter. When the pipe is open, the pump can affect the second tank indirectly. The system is controllable. When the pipe is effectively closed, the second tank is isolated from the pump. The rank of the controllability matrix drops to $1$, and the system is not controllable no matter how clever the controller is.

This is the kind of situation that shows up in larger hydraulic networks too. A valve status changes. A pipe has negligible sensitivity around the current operating point. A district is weakly connected. Then a maneuver that looked reasonable in one operating regime becomes impossible in another. The mathematical word is uncontrollability, but the physical story is simpler. The input has no path into the direction you are asking it to move.

The Certificate Pursuit

Now I wanna show you the main idea of my L-CSS paper with Kazma and Abdallah. Consider

$$ A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}, \qquad B = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}. \tag{12} $$

The third state is never actuated. The dynamics can amplify it by a factor of $3$, but the input cannot directly affect it. If the desired displacement is

$$ \Delta x = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \tag{13} $$

then the target asks for motion in the third coordinate. That is impossible. The PBH test finds this immediately: the left eigenvector

$$ w = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \tag{14} $$

satisfies the PBH invisibility condition in (7). This mode is invisible to the input. But notice another fact. The same vector $w$ also satisfies

$$ C_N^T w = 0, \qquad w^T \Delta x = 1. \tag{15} $$

The first relation in (15) says $w$ is orthogonal to everything the input can produce. The second relation in (15) says the target has a nonzero component in that forbidden direction. That is already an infeasibility certificate. This was easy to compute because the example is simple, but how do you do so for a network with a million physical states?

Fredholm Alternative Is the Boss

I start with the observation that the reachability condition in (4) is just a linear equation. Less than a year ago at a coffeeshop, I wrote (4) in a notebook and was trying to figure out a way to quantify uncontrollability of linear systems. I am now at the same coffeeshop writing this blog. In all fairness, I am at this coffeeshop, Elegy WeHo, like five times a week, so it is no special feat.

Anyway, I figured that if I wanted to draw meaningful intuition from the infeasibility of (4), I needed to look at infeasibility certificates in convex optimization. There is a classical theorem, the Fredholm Alternative, that says a linear system like (4) is infeasible if and only if there exists a vector $y$ such that

$$ C_N^T y = 0, \qquad y^T \Delta x \neq 0. \tag{16} $$

Basically vector $y$ is perpendicular to every reachable direction, but it is not perpendicular to the target. So the target cannot be reached. This is the same idea as a separating hyperplane in convex geometry too. If a point is outside a subspace, there is a direction that separates the point from that subspace.

Optimization people see this all the time. If a convex optimization problem is infeasible, solvers often return a dual ray or certificate. The certificate is a compact proof that the requested constraints cannot be satisfied, and control theory should use this habit more often.

My initial inclination was to give an uncontrollable system to an optimization solver and let the solver spit out the certificate. But when I tested this idea, I realized that the solver can take too much time even if the problem is infeasible. So while the idea was there, the implementation had to be different. I looked hard in the literature, but I found no precedent for this exact idea in quantifying uncontrollability or certifying infeasibility. Perhaps it is the community’s focus on controllability, or maybe the idea was too simple for anyone to find it as interesting as I did.

What the Paper Proves

The paper proves that optimization certificates and the PBH test are not separate stories. They are the same story viewed through two different lenses. The central result is:

Any infeasibility certificate $y$ lives in the uncontrollable subspace.

More explicitly, if $y$ satisfies the first condition in (16), then $y$ is a linear combination of uncontrollable generalized left eigenvectors of $A$. In the simple diagonalizable case, this looks like

$$ y = \sum_{j \in \mathcal{I}} \alpha_j w_j, \qquad \mathcal{I} = {j : w_j^T B = 0}. \tag{17} $$

Here $\mathcal{I}$ is the set of PBH-invisible modes, meaning the modes whose left eigenvectors satisfy the second condition in (7). So the certificate is not just a random separating vector. It is made of the PBH modes that the input cannot control. Let me summarize the narrative:

• PBH says uncontrollability is caused by input-invisible modes.
• Fredholm/Farkas says infeasibility is certified by separating directions.
• The paper shows that those separating directions are built from the input-invisible modes.

That means an optimization certificate can be used as a control diagnostic tool to rapidly tell an operator of a large network one of two things: (i) the maneuver $\Delta x$ is permissible or it is not, and (ii) if it is not possible, the certificate gives a concrete direction explaining why.

Speeding things

The paper shows that I do not need to build $C_N$ in (4) to search for certificates. This matters because the controllability matrix

$$ C_N = [B, AB, A^2B, \ldots, A^{N-1}B] \tag{18} $$

can be enormous. It can be dense even when $A$ is sparse. It can be ill-conditioned. It can make a clean idea computationally clumsy. It is the kind of problem the control community should focus on more, in my view.

The certificate-first approach avoids forming $C_N$. The algorithms in the paper work with products involving $A$, $B$, and their transposes. This is where Krylov methods enter. These methods are common in matrix algebra and scientific computing. Fun fact I learned many years ago: Krylov methods are routinely used in Formula 1 and computational fluid dynamics. A Krylov method is basically a disciplined way of learning about a large matrix through repeated matrix-vector products:

$$ y, \quad A^T y, \quad (A^T)^2 y, \quad \ldots \tag{19} $$

Rather than diagonalize the whole matrix, the algorithm probes only the directions needed to find a certificate satisfying (16). In the paper, this is done by searching for directions that are nearly invisible to $B$. Numerically, the relevant certificate checks look like

$$ B^T y \approx 0, \qquad y^T \Delta x \neq 0. \tag{20} $$

For a true left eigenvector, checking $B^T y = 0$ is enough, because

$$ y^T A^k B = \lambda^k y^T B = 0 \tag{21} $$

for every $k$. Equation (21) is exactly the logic that lets the method avoid building $C_N$: the whole tower $B,AB,A^2B,\ldots$ disappears once the left direction is invisible to $B$. In short:

The certificate tells me what is impossible. Krylov methods let me find that certificate without building the enormous controllability matrix.

Why Infeasibility Certificates Should Be More Popular

Control theory has a long tradition of proving possibility. Stabilize this. Track that. Regulate this output. Steer this state. Minimize this energy. Place this pole. Satisfy this LMI (that no one wants to look at anymore).

But impossibility results are just as valuable. It is not because I am a cynic, but because knowing what you cannot do is just as important as knowing what you can. Sometimes more valuable. If the current actuator layout cannot produce a maneuver, an engineer should know that quickly. If a controller synthesis problem is infeasible, the certificate should not be treated as an annoying solver artifact. It may contain the most interesting information in the whole computation.

In the paper, I tested the method on large routing/traffic-style network models with planted uncontrollable modes. The point was to test dense and sparse networked dynamic systems where global spectral diagnostics become less attractive as the dimension grows. Various case studies showed that the certificates can be computed in a fraction of a second for linear systems with $n = 1000$. More results are in the paper.

The Takeaway

The old age controllability story says:

Build the controllability matrix, or check PBH, and decide whether the system can go anywhere.

The certificate story says:

Pick the maneuver you care about. If it is impossible, find a vector that proves it is impossible.

I think this is a very useful idea. It makes uncontrollability less like a disappointing failure of controllability and more like an object I can compute and certify.

Hope you enjoyed this as much as I enjoyed writing the paper!