Cyclic Subspaces and Companion Matrices

Definition Let $T \colon V \to V$ be linear and let $v \in V$. The orbit of $v$ under $T$ is the sequence

with $T^0 = I$. Suppose $v \ne 0$. Any $\dim V + 1$ vectors of $V$ are dependent, so there is a smallest positive integer $d$ for which $v, Tv, \dots, T^d v$ are linearly dependent, and $d \le \dim V$. By the choice of $d$ the vectors $v, Tv, \dots, T^{d-1} v$ are independent. In a nontrivial dependence among $v, Tv, \dots, T^d v$ the coefficient of $T^d v$ is not zero, since otherwise the earlier vectors would be dependent. Dividing by it gives the first dependence

and the scalars $a_0, \dots, a_{d-1} \in \mathbb{F}$ are unique because the earlier vectors are independent. Equivalently, $p(T)v = 0$ for the monic polynomial

Definition Let $T \colon V \to V$ be linear and $v \in V$. The cyclic subspace generated by $v$ is the span of its orbit,

For $v = 0$ it is $\{0\}$. For $v \ne 0$, let $d$ and $p$ come from the first dependence. Then the orbit basis $v, Tv, \dots, T^{d-1} v$ is a basis of $\mathcal{C}_T(v)$, so $\dim \mathcal{C}_T(v) = d$. The subspace is invariant under $T$, and it is contained in every $T$-invariant subspace that contains $v$. The minimal polynomial of the restriction of $T$ to $U = \mathcal{C}_T(v)$, written $T|_{U}$, is $p$. A polynomial $q$ satisfies $q(T)v = 0$ exactly when $p$ divides $q$, so in particular $p$ divides the minimal polynomial $\mu_T$.

For the proof, let $U$ be the span of the orbit basis. The operator sends $T^j v$ to $T^{j+1} v$, which lies in $U$ for $j < d - 1$, and it sends $T^{d-1} v$ to $T^d v$, which lies in $U$ by the first dependence. By linearity $T$ maps $U$ into $U$, and induction on $k$ puts every $T^k v$ in $U$. Hence $\mathcal{C}_T(v) = U$, and any invariant subspace containing $v$ contains every $T^k v$ and therefore $U$. Polynomials in $T$ commute, so $p(T)T^j v = T^j p(T) v = 0$ for every $j$, and $p(T)$ vanishes on $U$. A nonzero polynomial of degree less than $d$ that vanished on $U$ would vanish at $v$, which would be a dependence among the independent vectors $v, \dots, T^{d-1} v$. So $p$ is the monic annihilating polynomial of least degree for $T|_{U}$. Finally, if $q(T)v = 0$, the same commuting argument shows that $q(T)$ vanishes on $U$, so $p$ divides $q$. Conversely $q = hp$ gives $q(T)v = h(T)p(T)v = 0$.

Definition Let $n = \dim V \ge 1$ and let $T \colon V \to V$ be linear. A vector $v \in V$ is a cyclic vector for $T$ if $\mathcal{C}_T(v) = V$, that is, if $v, Tv, \dots, T^{n-1} v$ is a basis of $V$. If $T$ has a cyclic vector $v$ with first dependence $p$, then

Indeed, $p$ is the minimal polynomial of the restriction of $T$ to $\mathcal{C}_T(v) = V$, which is $T$ itself, so $\mu_T = p$ has degree $n$. By the Cayley-Hamilton theorem $\mu_T$ divides $\chi_T$, which is also monic of degree $n$, so the two are equal. Consequently an operator whose minimal polynomial has degree less than $n$ has no cyclic vector. The converse is also true over $\mathbb{R}$ and $\mathbb{C}$, so $T$ has a cyclic vector exactly when $\deg \mu_T = n$, but that direction needs a longer argument and is not proved here.

Definition Let $p(t) = t^d + a_{d-1} t^{d-1} + \cdots + a_1 t + a_0$ be a monic polynomial of degree $d \ge 1$ with coefficients in $\mathbb{F}$. Its companion matrix is the $d \times d$ matrix with ones directly below the diagonal, the negated coefficients in the last column, and zeros elsewhere,

If $v \ne 0$ has first dependence $p$, then the matrix of $T|_{U}$ on $U = \mathcal{C}_T(v)$ in the ordered orbit basis $(v, Tv, \dots, T^{d-1} v)$ is $C_p$. Column $j$ holds the coordinates of the image of the $j$th basis vector. The operator sends each orbit basis vector to the next one, which gives the ones below the diagonal, and it sends the last one to $T^d v$, whose coordinates $-a_0, \dots, -a_{d-1}$ come from the first dependence. Since $C_p e_j = e_{j+1}$ for $j < d$ and $C_p e_d$ is the last column, the vector $e_1$ is a cyclic vector for $C_p$ on $\mathbb{F}^d$ with first dependence $p$, so

Some books use the transpose, with the negated coefficients in the last row. It has the same characteristic polynomial.

Definition Let $p(t) = t^d + a_{d-1} t^{d-1} + \cdots + a_1 t + a_0$ be monic with coefficients in $\mathbb{F}$. A sequence $x_0, x_1, x_2, \dots$ of scalars, or of vectors in $V$, satisfies the linear recurrence with polynomial $p$ if

for every $k \ge 0$. The orbit $x_k = T^k v$ of a nonzero vector satisfies the recurrence of its first dependence $p$, because applying $T^k$ to $p(T)v = 0$ gives $T^k p(T) v = 0$, which is the recurrence at step $k$. For every linear functional $\ell \in V^{\vee}$, the scalar sequence $s_k = \ell(T^k v)$ satisfies the same recurrence, because $\ell$ is linear. The orbit also satisfies the recurrence of any monic polynomial $q$ with $q(T)v = 0$, such as $\mu_T$ or $\chi_T$, and among these the recurrence of $p$ has the least order.