1 Mathematical setting and definitions
1.1 State-space models and reachability problem
In modern control and linear systems, a dynamical system is often written in state-space form. The system has a state vector \(x(t)\in\mathbb{F}^n\) (over a field \(\mathbb{F}\), typically \(\mathbb{R}\)) and an input \(u(t)\) from a set of admissible signals. The reachability problem asks which states can be produced at a specified time (or over a time interval) starting from a given initial condition \(x(0)=x_0\).
Reachability is a property of the pair consisting of the system dynamics and the way inputs enter the model (e.g., matrices \(A\) and \(B\) in an LTI framework). If the model is linear and time-invariant, reachability can be studied using linear algebra rather than direct simulation over all input functions.
1.2 Reachable subspace as a set and as a span
For a fixed initial state \(x_0\), the reachable set at time \(T\), often denoted \(\mathcal{R}(T)\), is the set of all states \(x(T)\) attainable via admissible inputs. When the system is linear and the input set is not constrained in a way that breaks linearity, the reachable set is an affine set; with zero initial condition it becomes a linear subspace.
A reachable subspace (reachable space) commonly refers to the subspace of all states that can be reached from the origin using some admissible inputs over an allowed horizon (finite \(T\) or infinite time). In that setting, it can be characterized as the span of finitely many vectors generated by the dynamics and input matrices.
1.3 Relation to linear subspaces and invariance
The reachable subspace is generally not invariant under the system dynamics in the strict “for all inputs” sense, but it has strong algebraic consistency properties. For LTI systems, the set of states reachable from the origin satisfies closure properties under applying one more admissible evolution step with an appropriate choice of input. This closure under extended control action connects reachable spaces to iterated images of the input directions through the system operator.
Additionally, one can compare reachable subspaces with invariant subspaces of \(A\). In many decompositions, reachable and unreachability components correspond to complementary subspaces linked by invariance under the system dynamics.
2 Reachable subspaces in linear systems
2.1 Discrete-time LTI reachability formulation
2.1.1 State evolution under inputs
A discrete-time LTI system is written as \[ x_{k+1}=Ax_k+Bu_k, \] where \(A\in\mathbb{F}^{n\times n}\) and \(B\in\mathbb{F}^{n\times m}\). The input sequence is \((u_0,u_1,\dots)\). Given \(x_0\), the state at time \(k\) depends linearly on the initial state and on the input history.
2.1.1.1 Constructing the reachability set from finite input sequences
Fix a horizon \(T\). The set of states reachable at time \(T\) consists of all vectors of the form \(x_T\) obtained by choosing inputs \(u_0,\dots,u_{T-1}\). Using repeated substitution, \[ x_T = A^T x_0 + \sum_{i=0}^{T-1} A^{T-1-i}B\,u_i. \] When \(x_0=0\), every reachable state has the form \[ x_T=\sum_{i=0}^{T-1} A^{T-1-i}B\,u_i, \] so \(\mathcal{R}(T)\) is the column space of a matrix whose blocks are \(A^jB\) for appropriate exponents. As \(T\) increases, these spaces can grow until they stabilize at a limiting reachable subspace.
2.1.2 Reachable subspace from iterated dynamics
Define the reachable subspace over a horizon \(T\) as the linear span of all vectors obtainable using the system’s \(A\)-propagation of the input directions: \[ \mathcal{R}(T)=\operatorname{span}\{B,\,AB,\,A^2B,\dots,\,A^{T-1}B\}. \] For an infinite horizon (or when allowing arbitrarily large \(T\)), the reachable subspace is the span of all \(A^kB\) for \(k\ge 0\), which stabilizes after at most \(n\) distinct dimension-increasing steps in finite-dimensional settings.
2.2 Continuous-time LTI reachability formulation (high level)
2.2.1 Input influence over time via system operators
A continuous-time LTI system is typically \[ \dot{x}(t)=Ax(t)+Bu(t). \] With initial condition \(x(0)=x_0\), the solution can be expressed using the matrix exponential. The influence of inputs enters through an integral of the form \(\int_0^t e^{A(t-\tau)}B u(\tau)\,d\tau\). This shows that reachability depends on how the semigroup generated by \(A\) transports the input directions over time.
2.2.2 Reachable sets and time horizon
At a fixed time \(t=T\), reachable states from \(x_0=0\) form a subspace determined by the images of \(B\) under the operator family \(e^{At}\). Over increasing time horizons, these subspaces can grow toward a terminal reachable subspace that reflects the system’s ability to steer the state.
While the continuous-time integral representation is more analytical, the underlying algebraic structure aligns with the discrete-time picture: the reachable subspace is generated by repeatedly “pushing” the input directions through the system dynamics.
2.3 Initial-condition dependence and autonomous components
2.3.1 Effect of nonzero initial state
For \(x_0\neq 0\), the reachable set at time \(T\) becomes affine: \[ x_T \in A^T x_0 + \mathcal{R}(T), \] where \(\mathcal{R}(T)\) denotes the reachable subspace from the origin. Thus, initial conditions shift the reachable set but do not alter the direction subspace created by the inputs.
2.3.2 Decompositions into reachable and unreachabile parts
In many theoretical treatments, the state space is partitioned into parts associated with controllability/reachability and parts that cannot be affected by inputs (under the model assumptions). The unreachability component corresponds to directions that remain untouched because the input image never spans them even after propagation through \(A\).
Such decompositions underlie canonical forms and reductions: they allow one to isolate the degrees of freedom that can be influenced from those that evolve autonomously.
3 Algebraic characterizations and computational criteria
3.1 Reachability matrix and rank tests (discrete-time)
3.1.1 Building the reachability matrix
For the discrete-time system \(x_{k+1}=Ax_k+Bu_k\), the reachability matrix for horizon \(T=n\) is commonly defined as \[ \mathcal{C} = [\,B,\ AB,\ A^2B,\ \dots,\ A^{n-1}B\,], \] an \(n\times (mn)\) block matrix formed by concatenating the propagated input matrices. This matrix collects all potential directions that can contribute to the state starting from the origin in at most \(n\) steps.
3.1.2 Rank conditions for full reachability
The dimension of the reachable subspace equals the rank of the reachability matrix: \[ \dim(\mathcal{R}) = \operatorname{rank}(\mathcal{C}), \] where \(\mathcal{R}\) is the reachable subspace over sufficiently large time (often \(T=n\) suffices for stabilization in finite dimensions). Full reachability of the entire state space occurs exactly when \(\operatorname{rank}(\mathcal{C})=n\), meaning the reachable subspace coincides with \(\mathbb{F}^n\).
3.2 Minimal generating sets for the reachable subspace
3.2.1 Basis selection and dimension
To represent \(\mathcal{R}\) explicitly, one selects a basis of vectors spanning it. The number of basis vectors equals \(\dim(\mathcal{R})\). Computationally, a basis can be obtained by performing column-reduction (e.g., Gaussian elimination) on the set of columns of \(\mathcal{C}\), thereby producing a minimal independent generating set.
This basis is not unique: different sets of columns may span the same subspace. Nonetheless, any basis produced from the reachability matrix yields the correct reachable subspace.
3.2.2 Computing generators via subspace iteration
Instead of building \([B,AB,\dots]\) directly (which may be large), one can iteratively construct the reachable subspace: \[ \mathcal{R}_0=\operatorname{im}(B),\quad \mathcal{R}_{k+1}=\mathcal{R}_k + A\,\mathcal{R}_k. \] After at most \(n\) iterations, the process stabilizes. At each step, one maintains a basis for the current subspace and expands it by applying \(A\) to existing basis vectors, then re-orthogonalizing/re-reducing for numerical stability.
3.3 Equivalent characterizations
3.3.1 Controllability matrix viewpoint
In many texts, reachable subspaces are presented through a “controllability” matrix, which is essentially the same object as the reachability matrix for discrete-time LTI systems. The difference is mostly terminological: reachability focuses on what states can be obtained, while controllability emphasizes the ability to steer between initial and final states. Algebraically, both correspond to the rank and column spaces generated by \(A^kB\).
3.3.2 Duality with observability (conceptual)
There is a well-known duality between controllability (reachability) and observability. While reachability concerns how inputs inject influence into states, observability concerns how states produce measurable outputs. Conceptually, reachable subspaces for \((A,B)\) correspond under a dual construction to observable subspaces for \((A^\top,C^\top)\), linking rank tests and invariant conditions through linear-algebraic orthogonality.
3.3.3 Invariant subspace characterization (conceptual)
Reachability can also be described via invariant subspaces associated with the dynamics. The unreachability directions often form a subspace that is invariant under \(A\) and orthogonal to the input-injected directions. This invariant-subspace viewpoint provides a structural reason why some state components remain unaffected no matter how inputs are chosen.
4 Properties of reachable subspaces
4.1 Dimension bounds and growth with time horizon
For a discrete-time system, \(\mathcal{R}(T)\) is nondecreasing with \(T\) (allowing more time cannot reduce the set of reachable states). Consequently, the dimension \(\dim(\mathcal{R}(T))\) is monotone and bounded above by \(n\). In finite-dimensional linear systems, the reachable subspace stabilizes after finitely many steps; the stabilization time is related to the maximum length of a chain of distinct subspaces generated by repeated application of \(A\) to \(\operatorname{im}(B)\).
4.2 Closure under system action
Reachable spaces have a natural compatibility with the system dynamics. If a state \(x\) is reachable at time \(k\), then any state at time \(k+1\) formed as \(Ax + Bu\) (with \(u\) chosen appropriately) lies in the reachable set at time \(k+1\). This “one-step extension” under control is the fundamental operational property of reachable sets.
4.3 Sum and intersection behavior
4.3.1 Merging reachable sets from different input sets
If a system is driven by multiple input channels with matrices \(B_1\) and \(B_2\), the reachable subspace generated by \([B_1\ B_2]\) equals the span of the reachable subspaces produced by each channel family combined. More precisely, the reachable space from the origin for \(B=[B_1\ B_2]\) is the smallest subspace containing both \(\mathcal{R}_{B_1}\) and \(\mathcal{R}_{B_2}\). Thus, the combined reachability reflects algebraic merging of generated directions.
4.3.2 Common reachable components under composed systems
When considering two systems or two input policies that share dynamics, common reachable components can be characterized by intersections of the corresponding reachable subspaces. The intersection captures state directions reachable in both scenarios. Such intersections are important in model composition and in comparing controllability capabilities across variants of a model.
5 Graph and combinatorial perspectives
5.1 Reachability in directed graphs vs. linear systems
5.1.1 Adjacency and reachability via transitive closure
Reachability in directed graphs is defined by existence of directed paths. The transitive closure of an adjacency relation captures which vertices can be reached from others. Although linear systems add amplitude and algebraic structure, there is an analogy: propagation by \(A\) resembles moving along edges, while multiplication by \(B\) injects “starting points” along certain directions.
5.1.2 Matrix powers as reachability witnesses
In graph theory, the \((i,j)\)-entry of \(A^k\) (for adjacency matrix \(A\), over appropriate algebra) counts or indicates walks of length \(k\). In linear systems, matrices like \(A^kB\) similarly collect the effect of \(k\) steps of dynamics applied to input directions. The resemblance is structural: both use iterated multiplication to reveal how influence spreads through repeated application of a rule.
5.2 Relation to spanning subspaces from walks
5.2.1 Walk-based constructions (intuition)
Each column of \(A^kB\) can be interpreted as a “walk” of length \(k\) starting from an input-injected direction and arriving at a state direction after repeated dynamics. While a linear system’s influence is continuous (not just boolean), the set of possible directions aligns with the span of contributions associated with such walks.
5.2.2 From combinatorial paths to linear generators
Under suitable bases and structural assumptions, one can map which state directions can be generated from which input directions by considering paths in an associated directed graph. The linear-algebraic consequence is that reachable subspaces correspond to spans generated by those path-induced direction vectors. This viewpoint helps connect controllability-related computations to combinatorial patterns.
6 Connections to controllability and canonical decompositions
6.1 Controllability as full-dimensional reachability
For LTI systems with the origin as reference, the system is controllable (in the linear sense) if the reachable subspace equals the whole state space. In discrete-time, controllability means any state can be reached from any initial state within some finite horizon (or, equivalently in linear settings, reachable subspace has full dimension). Hence, controllability can be read directly from the dimension/rank of the reachable subspace.
6.2 Decomposing the state space using reachable subspaces
6.2.1 Reachable/unreachable decomposition (conceptual)
A canonical decomposition divides the state space into components: those affected by inputs and those that evolve without input influence. The reachable portion is spanned by propagated input directions, while the unreachable part is orthogonal to those directions in a manner consistent with the system dynamics. This split is not merely definitional; it constrains the structure of \(A\) and \(B\) after a change of basis.
6.2.2 Implications for system reduction
Once the reachable subspace is known, one can reduce models by focusing on controllable modes and ignoring purely unactuated directions when designing controllers. The reduction is algebraic rather than heuristic: by representing the state in coordinates adapted to the reachable subspace, one obtains a block structure that clarifies which states can be manipulated and which cannot.
7 Examples and worked computations
7.1 Small-dimensional discrete-time examples
7.1.1 Computing a reachable subspace by hand
Consider a two-dimensional system with \[ A=\begin{bmatrix}1&1\\0&1\end{bmatrix},\quad B=\begin{bmatrix}1\\0\end{bmatrix}. \] The propagated input directions are \[ B=\begin{bmatrix}1\\0\end{bmatrix},\quad AB=\begin{bmatrix}1\\0\end{bmatrix},\quad A^2B=\begin{bmatrix}1\\0\end{bmatrix},\ \dots \] All vectors lie in the span of \(\begin{bmatrix}1\\0\end{bmatrix}\). Therefore the reachable subspace from the origin is one-dimensional: \[ \mathcal{R}=\operatorname{span}\left\{\begin{bmatrix}1\\0\end{bmatrix}\right\}. \] Even with arbitrarily long time, the second state coordinate cannot be independently generated from the input.
7.1.2 Rank-based verification
For \(n=2\), the reachability matrix is \[ \mathcal{C}=[\,B\ AB\,]= \left[\begin{array}{cc} 1 & 1\\ 0 & 0 \end{array}\right]. \] Its rank is \(1\), matching the computed reachable subspace dimension. Full reachability would require rank \(2\).
7.2 Example illustrating time-horizon growth
Let \[ A=\begin{bmatrix}0&1\\0&0\end{bmatrix},\quad B=\begin{bmatrix}1\\0\end{bmatrix}. \] Then \(B=\begin{bmatrix}1\\0\end{bmatrix}\) and \[ AB=\begin{bmatrix}0\\0\end{bmatrix}. \] So \(\mathcal{R}(1)=\operatorname{span}\{B\}\) is one-dimensional, while \(\mathcal{R}(2)=\mathcal{R}(1)\). In this example the reachable subspace stabilizes immediately, illustrating that more horizon does not always increase reachability.
In other systems, \(\mathcal{R}(T)\) grows for several steps before stabilizing, reflecting a “chain” of input propagation directions through repeated action of \(A\).
7.3 Example with multiple inputs and basis extraction
Take \(n=3\) with \[ A=\begin{bmatrix} 0&1&0\\ 0&0&1\\ 0&0&0 \end{bmatrix},\quad B=\begin{bmatrix} 1&0\\ 0&1\\ 0&0 \end{bmatrix}. \] Compute the generators: \[ B=\left\{\begin{bmatrix}1\\0\\0\end{bmatrix},\begin{bmatrix}0\\1\\0\end{bmatrix}\right\},\quad AB=\left\{\begin{bmatrix}0\\0\\0\end{bmatrix},\begin{bmatrix}0\\0\\0\end{bmatrix}\right\}, \quad A^2B=\{\cdots\}= \left\{\begin{bmatrix}0\\0\\0\end{bmatrix}\right\}. \] Here \(AB\) and higher powers contribute nothing additional beyond \(B\). The reachable subspace is therefore \[ \mathcal{R}=\operatorname{span}\left\{ \begin{bmatrix}1\\0\\0\end{bmatrix}, \begin{bmatrix}0\\1\\0\end{bmatrix} \right\}, \] which has dimension \(2\). A basis extraction step would yield exactly these two independent columns from the reachability matrix.
8 Common pitfalls and conventions
8.1 Distinguishing reachable subspaces from trajectories
A reachable subspace describes the set of attainable states (directions) and has algebraic meaning. Individual state trajectories depend on the chosen input sequence and can be far more detailed than the subspace. It is a common mistake to interpret the reachable subspace as containing entire time histories; it only characterizes the state set at a chosen time (or over a horizon), not the evolution path.
8.2 Finite vs. infinite time horizons
Results differ depending on whether reachability is defined at a fixed horizon \(T\), up to time \(T\), or for arbitrarily large time. For LTI systems with rank-stabilization, the infinite-horizon reachable subspace equals \(\mathcal{R}(n)\) in many discrete-time formulations, but one should check the specific definition used. Mixing these conventions can lead to incorrect dimension statements.
8.3 Numerical considerations for rank and basis computations
In practical computation, the rank of the reachability matrix can be sensitive to numerical conditioning, especially when \(A\) has eigenvalues that produce nearly dependent columns in \(A^kB\). Robust implementations often use tolerances or singular value decompositions rather than exact rank. Basis construction via iterative subspace updates similarly requires careful re-orthogonalization to avoid loss of independence due to floating-point errors.