In previous lessons, controllability was tested for a fully specified continuous-time LTI system \( \dot{\mathbf{x} } = A\mathbf{x} + B\mathbf{u} \) by the Kalman matrix \( \mathcal{C}=[B\;AB\;A^2B\;\cdots\;A^{n-1}B] \) and the PBH rank test. Structural controllability replaces numerical entries by a pattern. A pattern entry is either fixed zero or a free nonzero parameter.

\[ \bar A \in \{0,*\}^{n\times n},\qquad \bar B \in \{0,*\}^{n\times m} \]

The corresponding structured family is the set of all numerical pairs that respect this zero/nonzero pattern:

\[ \mathfrak{S}(\bar A,\bar B)= \left\{(A,B): \begin{aligned} & A_{ij}=0 \text{ if } \bar A_{ij}=0,\quad B_{ik}=0 \text{ if } \bar B_{ik}=0,\\ & A_{ij},B_{ik} \text{ are free where the pattern has } * \end{aligned} \right\}. \]

The pair \( (\bar A,\bar B) \) is called structurally controllable if there exists at least one numerical realization \( (A,B)\in\mathfrak{S}(\bar A,\bar B) \) whose Kalman controllability matrix has rank \( n \). A key algebraic fact then says that controllability holds for almost all choices of the free parameters, except possibly on a lower-dimensional algebraic set where exact cancellations occur.

\[ (\bar A,\bar B) \text{ structurally controllable} \quad \Longleftrightarrow \quad \operatorname{grank}\,\mathcal{C}(A,B)=n. \]

Here \( \operatorname{grank} \) means generic rank: the maximum rank obtainable by assigning numerical values to the free parameters.

Associate the structured pair with a directed graph \( \mathcal{G}(\bar A,\bar B) \). The graph has state vertices \( X=\{x_1,\dots,x_n\} \) and input vertices \( U=\{u_1,\dots,u_m\} \). The row-column convention is important:

• If \( \bar A_{ij}=* \), then state \( x_j \) directly influences \( \dot x_i \), so the graph contains an edge from \( x_j \) to \( x_i \).
• If \( \bar B_{ik}=* \), then input \( u_k \) directly influences \( \dot x_i \), so the graph contains an edge from \( u_k \) to \( x_i \).

flowchart TD
  A["Zero-star patterns Abar and Bbar"] --> B["Build directed graph"]
  B --> C["Edges: state columns to state rows"]
  B --> D["Edges: input columns to state rows"]
  C --> E["Check whether every state is input reachable"]
  D --> E
  E --> F["Build bipartite graph from columns to state rows"]
  F --> G{"Full generic row matching?"}
  G -->|"yes"| H["No dilation"]
  G -->|"no"| I["Dilation exists"]
  H --> J["Structurally controllable if reachability also holds"]
  I --> K["Structurally uncontrollable"]
        

This graph encodes possible influence paths, not exact gains. Therefore, structural controllability is a property of the architecture of the model: which state equations can depend on which states and which inputs.

The graph-theoretic test has two parts.

Condition 1: input accessibility. Every state vertex must be reachable from at least one input vertex through a directed path. If a state cannot be reached from any input in the graph, then no numerical choice of the free parameters can steer that state.

Condition 2: no dilation. For any subset of state vertices \( S\subseteq X \), define the in-neighbor set \( N^-(S) \) as all state or input vertices that have edges entering at least one vertex in \( S \). The no-dilation condition is

\[ |N^-(S)| \ge |S|,\qquad \forall S\subseteq X. \]

Intuitively, a dilation occurs when too many state equations depend on too few independent predecessor variables or input channels. Such a bottleneck prevents the generic controllability matrix from having full row rank.

A computationally convenient equivalent form uses a bipartite graph. Create left vertices for all state columns and input columns, and right vertices for all state rows. Add an edge from a left vertex to a right state-row vertex whenever the corresponding entry of \( [\bar A\;\bar B] \) is nonzero. Then no dilation is equivalent to the existence of a matching that covers all \( n \) right state-row vertices:

\[ \mu\big(\mathcal{B}([\bar A\;\bar B])\big)=n, \]

where \( \mu(\cdot) \) denotes the maximum matching size of the bipartite graph.

Theorem (generic graph test). The structured pair \( (\bar A,\bar B) \) is structurally controllable if and only if:

1. every state vertex is reachable from an input vertex, and
2. the system graph has no dilation, equivalently the bipartite graph of \( [\bar A\;\bar B] \) has a matching covering all state-row vertices.

Proof sketch. The Kalman matrix \( \mathcal{C}(A,B) \) contains polynomial functions of the free parameters. Its generic rank is the largest order of a minor whose determinant polynomial is not identically zero. Directed paths from inputs to states are necessary because an unreachable state row cannot receive any input-generated term in any block \( A^kB \). Therefore accessibility is necessary.

The no-dilation condition is a Hall-type condition. In the bipartite graph, a matching that covers all state rows selects one structurally independent predecessor for each state equation. Such a selection corresponds to a nonzero monomial term in a determinant expansion of an appropriate structured matrix. If no such matching exists, every candidate full-row minor must have determinant polynomial identically zero, so generic rank is less than \( n \). Combining accessibility with the full generic row-matching condition gives the structural form of the Kalman rank condition.

This theorem should be interpreted carefully. Structural controllability is not the same as saying that every numerical realization is controllable. It says controllability is generic: almost all admissible choices of the nonzero parameters are controllable. Exceptional numerical coincidences can still destroy rank.

Example A: a controllable chain. Consider a single-input three-state structure with \( u_1 \) entering \( x_1 \), \( x_1 \) influencing \( x_2 \), and \( x_2 \) influencing \( x_3 \).

\[ \bar A= \begin{bmatrix} 0&0&0\\ *&0&0\\ 0&*&0 \end{bmatrix}, \qquad \bar B= \begin{bmatrix} *\\0\\0 \end{bmatrix}. \]

All states are input reachable. The bipartite graph also has a full state-row matching: match the input column to row \( x_1 \), state column \( x_1 \) to row \( x_2 \), and state column \( x_2 \) to row \( x_3 \). Hence the pattern is structurally controllable.

Example B: reachable but not structurally controllable. Now let \( u_1 \) enter \( x_1 \), while \( x_1 \) influences both \( x_2 \) and \( x_3 \).

\[ \bar A= \begin{bmatrix} 0&0&0\\ *&0&0\\ *&0&0 \end{bmatrix}, \qquad \bar B= \begin{bmatrix} *\\0\\0 \end{bmatrix}. \]

Every state is reachable from the input, but the subset \( S=\{x_2,x_3\} \) has only one in-neighbor, \( N^-(S)=\{x_1\} \). Thus \( |N^-(S)|=1 \) while \( |S|=2 \), which is a dilation. The system is structurally uncontrollable.

flowchart LR
  subgraph C["Controllable chain"]
    U1["u1"] --> X1["x1"]
    X1 --> X2["x2"]
    X2 --> X3["x3"]
  end

  subgraph D["Reachable but dilation"]
    V1["u1"] --> Y1["x1"]
    Y1 --> Y2["x2"]
    Y1 --> Y3["x3"]
  end
        

Structural controllability does not replace the Kalman or PBH tests when numerical matrices are known. Instead, it answers an earlier design question: Does the zero/nonzero architecture even permit controllability generically?

\[ \begin{aligned} & \text{structural test passes} \quad \Longrightarrow \quad \operatorname{rank}[B\;AB\;\cdots\;A^{n-1}B]=n,\\ & \text{for almost all admissible numerical values.} \end{aligned} \]

Conversely, if the structural test fails, then the Kalman rank condition fails for every numerical realization respecting the same fixed-zero pattern.

A useful way to remember the distinction is:

• Kalman test: exact numerical rank of one \( (A,B) \).
• PBH test: exact numerical interaction between eigenvectors of \( A \) and columns of \( B \).
• Structural test: generic rank permitted by the zero/nonzero interconnection pattern.

In a physical system, a nonzero entry of \( \bar B \) represents an actuator channel that can directly affect a state equation. Structural controllability gives a fast first-pass actuator-placement criterion:

1. An actuator must create directed access to all state vertices through the system interconnection graph.
2. The placement must avoid dilation bottlenecks, so that the pattern can generically supply enough independent directions.

This is more qualitative than energy-based controllability. It does not tell us whether a state is easy or difficult to reach, nor whether the controllability Gramian is ill-conditioned. Those quantitative issues will be studied in Chapter 12. Here, the question is only whether controllability is structurally possible.

The following Python program implements the accessibility test and the full-row bipartite matching test from scratch. For larger research projects, networkx can be used for graph operations, while python-control and scipy remain useful for numerical state-space analysis after the structural pattern has passed this generic test.

Chapter11_Lesson4.py

# Chapter11_Lesson4.py
# Structural controllability graph test for xdot = A x + B u
# The pattern matrices Abar and Bbar use 1 for a free nonzero structural entry
# and 0 for a fixed zero entry.
#
# Test used in this lesson:
#   1. every state vertex is reachable from at least one input vertex;
#   2. the bipartite graph of [Abar Bbar] has a matching that covers all
#      state-row vertices.
#
# This implementation is intentionally written from scratch. For larger systems,
# Python users can also use networkx for graph traversal/matching and python-control
# for numerical state-space analysis.

from collections import deque
from typing import Dict, List, Tuple


def _validate_pattern(Abar: List[List[int]], Bbar: List[List[int]]) -> Tuple[int, int]:
    n = len(Abar)
    if n == 0:
        raise ValueError("Abar must be nonempty.")
    if any(len(row) != n for row in Abar):
        raise ValueError("Abar must be square.")
    if len(Bbar) != n:
        raise ValueError("Bbar must have the same number of rows as Abar.")
    m = len(Bbar[0])
    if m == 0:
        raise ValueError("Bbar must have at least one input column.")
    if any(len(row) != m for row in Bbar):
        raise ValueError("All rows of Bbar must have the same length.")
    return n, m


def _input_reachable_states(Abar: List[List[int]], Bbar: List[List[int]]) -> List[bool]:
    n, m = _validate_pattern(Abar, Bbar)

    # Vertices 0,...,n-1 are states x1,...,xn.
    # Vertices n,...,n+m-1 are inputs u1,...,um.
    adj = [[] for _ in range(n + m)]

    # Abar[i][j] means x_j influences xdot_i, hence x_j -> x_i.
    for i in range(n):
        for j in range(n):
            if Abar[i][j] != 0:
                adj[j].append(i)

    # Bbar[i][k] means u_k influences xdot_i, hence u_k -> x_i.
    for i in range(n):
        for k in range(m):
            if Bbar[i][k] != 0:
                adj[n + k].append(i)

    q = deque(range(n, n + m))
    seen = [False] * (n + m)
    for v in q:
        seen[v] = True

    while q:
        v = q.popleft()
        for w in adj[v]:
            if not seen[w]:
                seen[w] = True
                q.append(w)

    return seen[:n]


def _maximum_bipartite_matching_size(Abar: List[List[int]], Bbar: List[List[int]]) -> int:
    n, m = _validate_pattern(Abar, Bbar)
    left_count = n + m
    right_count = n

    # Left vertices: state columns x1,...,xn and input columns u1,...,um.
    # Right vertices: state rows x1,...,xn.
    adj_left = [[] for _ in range(left_count)]

    # Dynamic structural edges: left state column x_j -> right state row x_i.
    for i in range(n):
        for j in range(n):
            if Abar[i][j] != 0:
                adj_left[j].append(i)

    # Input structural edges: left input column u_k -> right state row x_i.
    for i in range(n):
        for k in range(m):
            if Bbar[i][k] != 0:
                adj_left[n + k].append(i)

    pair_u = [-1] * left_count
    pair_v = [-1] * right_count
    dist = [0] * left_count

    def bfs() -> bool:
        q = deque()
        found_free_right = False
        for u in range(left_count):
            if pair_u[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = -1

        while q:
            u = q.popleft()
            for v in adj_left[u]:
                mate = pair_v[v]
                if mate == -1:
                    found_free_right = True
                elif dist[mate] == -1:
                    dist[mate] = dist[u] + 1
                    q.append(mate)
        return found_free_right

    def dfs(u: int) -> bool:
        for v in adj_left[u]:
            mate = pair_v[v]
            if mate == -1 or (dist[mate] == dist[u] + 1 and dfs(mate)):
                pair_u[u] = v
                pair_v[v] = u
                return True
        dist[u] = -1
        return False

    matching = 0
    while bfs():
        for u in range(left_count):
            if pair_u[u] == -1 and dfs(u):
                matching += 1
    return matching


def structural_controllability(Abar: List[List[int]], Bbar: List[List[int]]) -> Dict[str, object]:
    n, _ = _validate_pattern(Abar, Bbar)
    reachable = _input_reachable_states(Abar, Bbar)
    matching_size = _maximum_bipartite_matching_size(Abar, Bbar)

    return {
        "all_states_input_reachable": all(reachable),
        "reachable_state_flags": reachable,
        "maximum_matching_size": matching_size,
        "no_dilation_via_full_row_matching": matching_size == n,
        "structurally_controllable": all(reachable) and matching_size == n,
    }


if __name__ == "__main__":
    # Example 1: u1 -> x1 -> x2 -> x3 is structurally controllable.
    A_chain = [
        [0, 0, 0],
        [1, 0, 0],
        [0, 1, 0],
    ]
    B_chain = [
        [1],
        [0],
        [0],
    ]

    # Example 2: u1 -> x1, x1 -> x2, x1 -> x3 is reachable but has a dilation.
    A_dilation = [
        [0, 0, 0],
        [1, 0, 0],
        [1, 0, 0],
    ]
    B_dilation = [
        [1],
        [0],
        [0],
    ]

    print("Chain example:")
    print(structural_controllability(A_chain, B_chain))

    print("\nDilation example:")
    print(structural_controllability(A_dilation, B_dilation))

The C++ version uses only the standard library and implements a Hopcroft-Karp maximum bipartite matching algorithm. In a larger control codebase, Eigen can be added for numerical Kalman-rank computations after structural screening.

Chapter11_Lesson4.cpp

// Chapter11_Lesson4.cpp
// Structural controllability graph test for xdot = A x + B u.
// Pattern entries: 1 = free structural nonzero, 0 = fixed zero.
// Compile:
//   g++ -std=c++17 -O2 Chapter11_Lesson4.cpp -o Chapter11_Lesson4

#include <iostream>
#include <vector>
#include <queue>
#include <stdexcept>
#include <string>

using Matrix = std::vector<std::vector<int>>;

struct Result {
    bool reachable;
    bool fullMatching;
    bool structurallyControllable;
    int matchingSize;
    std::vector<bool> reachableStates;
};

void validatePattern(const Matrix& Abar, const Matrix& Bbar, int& n, int& m) {
    n = static_cast<int>(Abar.size());
    if (n == 0) throw std::runtime_error("Abar must be nonempty.");
    for (const auto& row : Abar) {
        if (static_cast<int>(row.size()) != n) throw std::runtime_error("Abar must be square.");
    }
    if (static_cast<int>(Bbar.size()) != n) throw std::runtime_error("Bbar row count must match Abar.");
    m = static_cast<int>(Bbar[0].size());
    if (m == 0) throw std::runtime_error("Bbar must have at least one input column.");
    for (const auto& row : Bbar) {
        if (static_cast<int>(row.size()) != m) throw std::runtime_error("Bbar rows must have equal length.");
    }
}

std::vector<bool> inputReachability(const Matrix& Abar, const Matrix& Bbar) {
    int n, m;
    validatePattern(Abar, Bbar, n, m);

    std::vector<std::vector<int>> adj(n + m);

    // Abar[i][j] means x_j influences xdot_i, so x_j -> x_i.
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (Abar[i][j] != 0) adj[j].push_back(i);

    // Bbar[i][k] means u_k influences xdot_i, so u_k -> x_i.
    for (int i = 0; i < n; ++i)
        for (int k = 0; k < m; ++k)
            if (Bbar[i][k] != 0) adj[n + k].push_back(i);

    std::vector<bool> seen(n + m, false);
    std::queue<int> q;
    for (int k = 0; k < m; ++k) {
        seen[n + k] = true;
        q.push(n + k);
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int w : adj[v]) {
            if (!seen[w]) {
                seen[w] = true;
                q.push(w);
            }
        }
    }

    return std::vector<bool>(seen.begin(), seen.begin() + n);
}

class HopcroftKarp {
public:
    HopcroftKarp(int leftCount, int rightCount, std::vector<std::vector<int>> adj)
        : L(leftCount), R(rightCount), adjLeft(std::move(adj)),
          pairU(L, -1), pairV(R, -1), dist(L, -1) {}

    int maximumMatching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < L; ++u) {
                if (pairU[u] == -1 && dfs(u)) ++matching;
            }
        }
        return matching;
    }

private:
    int L, R;
    std::vector<std::vector<int>> adjLeft;
    std::vector<int> pairU, pairV, dist;

    bool bfs() {
        std::queue<int> q;
        bool foundFreeRight = false;
        for (int u = 0; u < L; ++u) {
            if (pairU[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = -1;
            }
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adjLeft[u]) {
                int mate = pairV[v];
                if (mate == -1) {
                    foundFreeRight = true;
                } else if (dist[mate] == -1) {
                    dist[mate] = dist[u] + 1;
                    q.push(mate);
                }
            }
        }
        return foundFreeRight;
    }

    bool dfs(int u) {
        for (int v : adjLeft[u]) {
            int mate = pairV[v];
            if (mate == -1 || (dist[mate] == dist[u] + 1 && dfs(mate))) {
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }
};

int maximumPatternMatchingSize(const Matrix& Abar, const Matrix& Bbar) {
    int n, m;
    validatePattern(Abar, Bbar, n, m);
    int leftCount = n + m;
    int rightCount = n;
    std::vector<std::vector<int>> adjLeft(leftCount);

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (Abar[i][j] != 0) adjLeft[j].push_back(i);

    for (int i = 0; i < n; ++i)
        for (int k = 0; k < m; ++k)
            if (Bbar[i][k] != 0) adjLeft[n + k].push_back(i);

    HopcroftKarp hk(leftCount, rightCount, adjLeft);
    return hk.maximumMatching();
}

Result structuralControllability(const Matrix& Abar, const Matrix& Bbar) {
    int n, m;
    validatePattern(Abar, Bbar, n, m);
    auto reachableStates = inputReachability(Abar, Bbar);
    bool allReachable = true;
    for (bool flag : reachableStates) allReachable = allReachable && flag;

    int matchingSize = maximumPatternMatchingSize(Abar, Bbar);
    bool fullMatching = (matchingSize == n);

    return {allReachable, fullMatching, allReachable && fullMatching, matchingSize, reachableStates};
}

void printResult(const std::string& title, const Result& r) {
    std::cout << title << "\n";
    std::cout << "  all states input reachable: " << (r.reachable ? "true" : "false") << "\n";
    std::cout << "  matching size: " << r.matchingSize << "\n";
    std::cout << "  no dilation via full row matching: " << (r.fullMatching ? "true" : "false") << "\n";
    std::cout << "  structurally controllable: " << (r.structurallyControllable ? "true" : "false") << "\n";
}

int main() {
    Matrix Achain = {
        {0, 0, 0},
        {1, 0, 0},
        {0, 1, 0}
    };
    Matrix Bchain = {
        {1},
        {0},
        {0}
    };

    Matrix Adilation = {
        {0, 0, 0},
        {1, 0, 0},
        {1, 0, 0}
    };
    Matrix Bdilation = {
        {1},
        {0},
        {0}
    };

    printResult("Chain example", structuralControllability(Achain, Bchain));
    printResult("Dilation example", structuralControllability(Adilation, Bdilation));
    return 0;
}

The Java version is suitable for software-engineering contexts where graph-based control analysis is integrated into a larger application. It uses standard Java collections and avoids external dependencies.

Chapter11_Lesson4.java

// Chapter11_Lesson4.java
// Structural controllability graph test for xdot = A x + B u.
// Pattern entries: 1 = free structural nonzero, 0 = fixed zero.
// Compile and run:
//   javac Chapter11_Lesson4.java
//   java Chapter11_Lesson4

import java.util.*;

public class Chapter11_Lesson4 {
    static class Result {
        boolean reachable;
        boolean fullMatching;
        boolean structurallyControllable;
        int matchingSize;
        boolean[] reachableStates;

        Result(boolean reachable, boolean fullMatching, boolean structurallyControllable,
               int matchingSize, boolean[] reachableStates) {
            this.reachable = reachable;
            this.fullMatching = fullMatching;
            this.structurallyControllable = structurallyControllable;
            this.matchingSize = matchingSize;
            this.reachableStates = reachableStates;
        }
    }

    static int[] validatePattern(int[][] Abar, int[][] Bbar) {
        int n = Abar.length;
        if (n == 0) throw new IllegalArgumentException("Abar must be nonempty.");
        for (int[] row : Abar) {
            if (row.length != n) throw new IllegalArgumentException("Abar must be square.");
        }
        if (Bbar.length != n) throw new IllegalArgumentException("Bbar row count must match Abar.");
        int m = Bbar[0].length;
        if (m == 0) throw new IllegalArgumentException("Bbar must have at least one input column.");
        for (int[] row : Bbar) {
            if (row.length != m) throw new IllegalArgumentException("Bbar rows must have equal length.");
        }
        return new int[] {n, m};
    }

    static boolean[] inputReachability(int[][] Abar, int[][] Bbar) {
        int[] dim = validatePattern(Abar, Bbar);
        int n = dim[0];
        int m = dim[1];

        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n + m; v++) adj.add(new ArrayList<>());

        // Abar[i][j] means x_j influences xdot_i, so x_j -> x_i.
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (Abar[i][j] != 0) adj.get(j).add(i);

        // Bbar[i][k] means u_k influences xdot_i, so u_k -> x_i.
        for (int i = 0; i < n; i++)
            for (int k = 0; k < m; k++)
                if (Bbar[i][k] != 0) adj.get(n + k).add(i);

        boolean[] seen = new boolean[n + m];
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int k = 0; k < m; k++) {
            seen[n + k] = true;
            q.add(n + k);
        }

        while (!q.isEmpty()) {
            int v = q.remove();
            for (int w : adj.get(v)) {
                if (!seen[w]) {
                    seen[w] = true;
                    q.add(w);
                }
            }
        }

        return Arrays.copyOf(seen, n);
    }

    static class HopcroftKarp {
        int L, R;
        List<List<Integer>> adjLeft;
        int[] pairU, pairV, dist;

        HopcroftKarp(int leftCount, int rightCount, List<List<Integer>> adjLeft) {
            this.L = leftCount;
            this.R = rightCount;
            this.adjLeft = adjLeft;
            this.pairU = new int[L];
            this.pairV = new int[R];
            this.dist = new int[L];
            Arrays.fill(pairU, -1);
            Arrays.fill(pairV, -1);
        }

        boolean bfs() {
            ArrayDeque<Integer> q = new ArrayDeque<>();
            boolean foundFreeRight = false;

            for (int u = 0; u < L; u++) {
                if (pairU[u] == -1) {
                    dist[u] = 0;
                    q.add(u);
                } else {
                    dist[u] = -1;
                }
            }

            while (!q.isEmpty()) {
                int u = q.remove();
                for (int v : adjLeft.get(u)) {
                    int mate = pairV[v];
                    if (mate == -1) {
                        foundFreeRight = true;
                    } else if (dist[mate] == -1) {
                        dist[mate] = dist[u] + 1;
                        q.add(mate);
                    }
                }
            }
            return foundFreeRight;
        }

        boolean dfs(int u) {
            for (int v : adjLeft.get(u)) {
                int mate = pairV[v];
                if (mate == -1 || (dist[mate] == dist[u] + 1 && dfs(mate))) {
                    pairU[u] = v;
                    pairV[v] = u;
                    return true;
                }
            }
            dist[u] = -1;
            return false;
        }

        int maximumMatching() {
            int matching = 0;
            while (bfs()) {
                for (int u = 0; u < L; u++) {
                    if (pairU[u] == -1 && dfs(u)) matching++;
                }
            }
            return matching;
        }
    }

    static int maximumPatternMatchingSize(int[][] Abar, int[][] Bbar) {
        int[] dim = validatePattern(Abar, Bbar);
        int n = dim[0];
        int m = dim[1];

        int leftCount = n + m;
        int rightCount = n;
        List<List<Integer>> adjLeft = new ArrayList<>();
        for (int u = 0; u < leftCount; u++) adjLeft.add(new ArrayList<>());

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (Abar[i][j] != 0) adjLeft.get(j).add(i);

        for (int i = 0; i < n; i++)
            for (int k = 0; k < m; k++)
                if (Bbar[i][k] != 0) adjLeft.get(n + k).add(i);

        return new HopcroftKarp(leftCount, rightCount, adjLeft).maximumMatching();
    }

    static Result structuralControllability(int[][] Abar, int[][] Bbar) {
        int[] dim = validatePattern(Abar, Bbar);
        int n = dim[0];

        boolean[] reach = inputReachability(Abar, Bbar);
        boolean allReachable = true;
        for (boolean flag : reach) allReachable = allReachable && flag;

        int matchingSize = maximumPatternMatchingSize(Abar, Bbar);
        boolean fullMatching = matchingSize == n;

        return new Result(allReachable, fullMatching, allReachable && fullMatching, matchingSize, reach);
    }

    static void printResult(String title, Result r) {
        System.out.println(title);
        System.out.println("  all states input reachable: " + r.reachable);
        System.out.println("  matching size: " + r.matchingSize);
        System.out.println("  no dilation via full row matching: " + r.fullMatching);
        System.out.println("  structurally controllable: " + r.structurallyControllable);
    }

    public static void main(String[] args) {
        int[][] Achain = {
            {0, 0, 0},
            {1, 0, 0},
            {0, 1, 0}
        };
        int[][] Bchain = {
            {1},
            {0},
            {0}
        };

        int[][] Adilation = {
            {0, 0, 0},
            {1, 0, 0},
            {1, 0, 0}
        };
        int[][] Bdilation = {
            {1},
            {0},
            {0}
        };

        printResult("Chain example", structuralControllability(Achain, Bchain));
        printResult("Dilation example", structuralControllability(Adilation, Bdilation));
    }
}

The MATLAB script implements the same structural test. If a Simulink model is linearized into a state-space object, its numerical matrices can be converted into structural patterns by thresholding the nonzero entries. The structural test can then be applied before running ordinary numerical controllability checks such as rank(ctrb(A,B)).

Chapter11_Lesson4.m

% Chapter11_Lesson4.m
% Structural controllability graph test for xdot = A x + B u.
% Pattern entries: 1 = free structural nonzero, 0 = fixed zero.
%
% Simulink note:
% If a linearized Simulink model is available as sys = linearize("modelName",io),
% then a structural pattern can be formed by
%   Abar = double(abs(sys.A) > tol);
%   Bbar = double(abs(sys.B) > tol);
% and then tested with structuralControllability(Abar,Bbar).

clear; clc;

A_chain = [0 0 0;
           1 0 0;
           0 1 0];
B_chain = [1; 0; 0];

A_dilation = [0 0 0;
              1 0 0;
              1 0 0];
B_dilation = [1; 0; 0];

disp("Chain example");
disp(structuralControllability(A_chain, B_chain));

disp("Dilation example");
disp(structuralControllability(A_dilation, B_dilation));

function result = structuralControllability(Abar, Bbar)
    [n, ~] = validatePattern(Abar, Bbar);
    reach = inputReachability(Abar, Bbar);
    matchingSize = maximumPatternMatchingSize(Abar, Bbar);
    
    result = struct();
    result.all_states_input_reachable = all(reach);
    result.reachable_state_flags = reach;
    result.maximum_matching_size = matchingSize;
    result.no_dilation_via_full_row_matching = (matchingSize == n);
    result.structurally_controllable = all(reach) && (matchingSize == n);
end

function [n, m] = validatePattern(Abar, Bbar)
    [n1, n2] = size(Abar);
    if n1 ~= n2
        error("Abar must be square.");
    end
    [bRows, m] = size(Bbar);
    if bRows ~= n1
        error("Bbar row count must match Abar.");
    end
    if m == 0
        error("Bbar must have at least one input column.");
    end
    n = n1;
end

function reach = inputReachability(Abar, Bbar)
    [n, m] = validatePattern(Abar, Bbar);
    N = n + m;
    adj = cell(N, 1);
    for v = 1:N
        adj{v} = [];
    end
    
    % Abar(i,j) means x_j influences xdot_i, so x_j -> x_i.
    for i = 1:n
        for j = 1:n
            if Abar(i,j) ~= 0
                adj{j} = [adj{j}, i];
            end
        end
    end
    
    % Bbar(i,k) means u_k influences xdot_i, so u_k -> x_i.
    for i = 1:n
        for k = 1:m
            if Bbar(i,k) ~= 0
                adj{n+k} = [adj{n+k}, i];
            end
        end
    end
    
    seen = false(N, 1);
    q = zeros(N, 1);
    head = 1; tail = 0;
    
    for k = 1:m
        tail = tail + 1;
        q(tail) = n + k;
        seen(n+k) = true;
    end
    
    while head <= tail
        v = q(head);
        head = head + 1;
        for w = adj{v}
            if ~seen(w)
                seen(w) = true;
                tail = tail + 1;
                q(tail) = w;
            end
        end
    end
    
    reach = seen(1:n).';
end

function matchingSize = maximumPatternMatchingSize(Abar, Bbar)
    [n, m] = validatePattern(Abar, Bbar);
    leftCount = n + m;
    rightCount = n;
    adjLeft = cell(leftCount, 1);
    for u = 1:leftCount
        adjLeft{u} = [];
    end
    
    for i = 1:n
        for j = 1:n
            if Abar(i,j) ~= 0
                adjLeft{j} = [adjLeft{j}, i];
            end
        end
    end
    
    for i = 1:n
        for k = 1:m
            if Bbar(i,k) ~= 0
                adjLeft{n+k} = [adjLeft{n+k}, i];
            end
        end
    end
    
    pairV = zeros(rightCount, 1);
    matchingSize = 0;
    
    for u = 1:leftCount
        visited = false(rightCount, 1);
        if augment(u, visited)
            matchingSize = matchingSize + 1;
        end
    end
    
    function ok = augment(u, visited)
        ok = false;
        for v = adjLeft{u}
            if visited(v)
                continue;
            end
            visited(v) = true;
            if pairV(v) == 0 || augment(pairV(v), visited)
                pairV(v) = u;
                ok = true;
                return;
            end
        end
    end
end

Mathematica is convenient for graph construction, visualization, and symbolic experimentation. The code below uses graph reachability and a maximum independent edge set to represent the bipartite matching.

Chapter11_Lesson4.nb

(* Chapter11_Lesson4.nb *)
(* Structural controllability graph test for xdot = A x + B u.
   Pattern entries: 1 = free structural nonzero, 0 = fixed zero. *)

ClearAll[StructuralControllabilityTest];

StructuralControllabilityTest[Abar_, Bbar_] := Module[
  {n, m, states, inputs, state, input, edgesA, edgesB, graph,
   reachable, allReachable, leftStates, leftInputs, rightStates,
   leftNameState, leftNameInput, rightNameState, edgesMatch, matchingGraph,
   matching, matchingSize, fullMatching},
  
  n = Length[Abar];
  m = Length[First[Bbar]];
  
  state[i_] := "x" <> ToString[i];
  input[k_] := "u" <> ToString[k];
  states = state /@ Range[n];
  inputs = input /@ Range[m];
  
  edgesA = Flatten[
    Table[
      If[Abar[[i, j]] != 0, DirectedEdge[state[j], state[i]], Nothing],
      {i, n}, {j, n}
    ]
  ];
  
  edgesB = Flatten[
    Table[
      If[Bbar[[i, k]] != 0, DirectedEdge[input[k], state[i]], Nothing],
      {i, n}, {k, m}
    ]
  ];
  
  graph = Graph[Join[inputs, states], Join[edgesA, edgesB], VertexLabels -> "Name"];
  reachable = Union @@ (VertexOutComponent[graph, #] & /@ inputs);
  allReachable = AllTrue[states, MemberQ[reachable, #] &];
  
  leftNameState[j_] := "Lx" <> ToString[j];
  leftNameInput[k_] := "Lu" <> ToString[k];
  rightNameState[i_] := "Rx" <> ToString[i];
  
  leftStates = leftNameState /@ Range[n];
  leftInputs = leftNameInput /@ Range[m];
  rightStates = rightNameState /@ Range[n];
  
  edgesMatch = Join[
    Flatten[
      Table[
        If[Abar[[i, j]] != 0,
          UndirectedEdge[leftNameState[j], rightNameState[i]],
          Nothing
        ],
        {i, n}, {j, n}
      ]
    ],
    Flatten[
      Table[
        If[Bbar[[i, k]] != 0,
          UndirectedEdge[leftNameInput[k], rightNameState[i]],
          Nothing
        ],
        {i, n}, {k, m}
      ]
    ]
  ];
  
  matchingGraph = Graph[Join[leftStates, leftInputs, rightStates], edgesMatch];
  matching = FindIndependentEdgeSet[matchingGraph];
  matchingSize = Length[matching];
  fullMatching = matchingSize == n;
  
  <|
    "AllStatesInputReachable" -> allReachable,
    "ReachableStates" -> Intersection[states, reachable],
    "MaximumMatchingSize" -> matchingSize,
    "NoDilationViaFullRowMatching" -> fullMatching,
    "StructurallyControllable" -> (allReachable && fullMatching),
    "DirectedGraph" -> graph,
    "MatchingGraph" -> matchingGraph
  |>
];

Achain = { {0, 0, 0}, {1, 0, 0}, {0, 1, 0} };
Bchain = { {1}, {0}, {0} };

Adilation = { {0, 0, 0}, {1, 0, 0}, {1, 0, 0} };
Bdilation = { {1}, {0}, {0} };

StructuralControllabilityTest[Achain, Bchain]
StructuralControllabilityTest[Adilation, Bdilation]

Problem 1 (Graph Construction): For \( \bar A=\begin{bmatrix}0&*&0\\0&0&*\\0&0&0\end{bmatrix} \) and \( \bar B=\begin{bmatrix}0\\0\\*\end{bmatrix} \), list the directed graph edges and decide whether all states are input reachable.

Solution: The nonzero entry \( \bar A_{12}=* \) gives the edge from \( x_2 \) to \( x_1 \). The entry \( \bar A_{23}=* \) gives the edge from \( x_3 \) to \( x_2 \). The input entry gives the edge from \( u_1 \) to \( x_3 \). Hence there is a directed chain from \( u_1 \) to \( x_3 \), then to \( x_2 \), then to \( x_1 \). All states are input reachable.

Problem 2 (Dilation): Consider the structure in Example B. Show directly that it violates the no-dilation condition.

Solution: Select \( S=\{x_2,x_3\} \). Both \( x_2 \) and \( x_3 \) receive their only incoming dynamic edge from \( x_1 \). There is no direct input edge into either state. Therefore \( N^-(S)=\{x_1\} \). Since \( |N^-(S)|=1 \) and \( |S|=2 \), the Hall-type inequality fails. The system is structurally uncontrollable even though every state is reachable from the input.

Problem 3 (Matching Interpretation): For the chain structure in Example A, construct a full matching in the bipartite graph of \( [\bar A\;\bar B] \).

Solution: The right vertices are the state rows \( x_1,x_2,x_3 \). The left vertices include state columns \( x_1,x_2,x_3 \) and the input column \( u_1 \). A full matching is:

\[ u_1 \text{ matched to row } x_1,\qquad x_1 \text{ matched to row } x_2,\qquad x_2 \text{ matched to row } x_3. \]

All three right state-row vertices are covered, so the no-dilation condition is satisfied.

Problem 4 (Generic vs Numerical Failure): Let \( \bar A=\begin{bmatrix}*&0\\0&*\end{bmatrix} \) and \( \bar B=\begin{bmatrix}*\\*\end{bmatrix} \). Show that this pattern is structurally controllable, but give one numerical realization that is uncontrollable.

Solution: Both states are directly input reachable. The bipartite graph can match the state-column vertex \( x_1 \) to row \( x_1 \) and the state-column vertex \( x_2 \) to row \( x_2 \), so the no-dilation condition holds. For a numerical realization

\[ A=\begin{bmatrix}a_1&0\\0&a_2\end{bmatrix},\qquad B=\begin{bmatrix}b_1\\b_2\end{bmatrix}, \]

the Kalman matrix is

\[ \mathcal{C}= \begin{bmatrix} b_1&a_1b_1\\ b_2&a_2b_2 \end{bmatrix}, \qquad \det(\mathcal{C})=b_1b_2(a_2-a_1). \]

This determinant is not the zero polynomial, so the pattern is structurally controllable. However, if \( a_1=a_2=1 \) and \( b_1=b_2=1 \), then \( \det(\mathcal{C})=0 \). This special numerical realization is uncontrollable even though the structure is generically controllable.

Problem 5 (Actuator Placement): For the chain \( x_1 \) influences \( x_2 \) and \( x_2 \) influences \( x_3 \), compare two placements: input into \( x_1 \) versus input into \( x_2 \).

Solution: If the input enters \( x_1 \), then the input can reach \( x_1,x_2,x_3 \) along the directed chain. A full matching also exists, so the structure is structurally controllable. If the input enters \( x_2 \), then \( x_1 \) is not reachable from the input because the dynamic edges go downstream from \( x_1 \) to \( x_2 \) to \( x_3 \). Thus accessibility fails, and the system is structurally uncontrollable.

Structural controllability studies whether the zero/nonzero pattern of \( A \) and \( B \) permits controllability generically. Its introductory graph test has two parts: every state must be reachable from an input, and there must be no dilation, equivalently a bipartite matching must cover all state-row vertices. This lesson connects the graph view to the Kalman rank condition and prepares the way for later discussions of actuator placement, Gramians, and controllability energy.