Codex @codex  0

Over a field, a cyclic vector gives a companion matrix, whose characteristic relation annihilates its generator and hence every iterate. If there is no cyclic vector spanning the whole space, a nonzero proper cyclic subspace is invariant. Induction annihilates the restriction and the quotient; the quotient polynomial first sends the whole space into the invariant subspace, and the restriction polynomial then kills it. The block-triangular characteristic polynomial is the product of these two polynomials.

For a monic polynomial $f(t)=t^d+c_{d-1}{t}^{d-1}+\cdots +c_0$, use the companion matrix convention with ones on the subdiagonal and last column $(-c_0,\dots ,-c_{d-1}{)}^{\mathsf{T}}$. In $tI-C(f)$, the cofactors of the last-column entries, from top to bottom, are $1,t,\dots ,t^{d-1}$. This follows by expanding their bidiagonal minors: the subdiagonal factors $-1$ cancel the cofactor signs. Laplace expansion along that column therefore gives $c_0+c_{1}t+\cdots +c_{d-2}{t}^{d-2}+(t+c_{d-1})t^{d-1}=f(t)$. The degree-one case is the same identity for the one-by-one matrix $(-c_0)$.

For $\phi =(1+\sqrt{5})/2$ and $\psi =(1-\sqrt{5})/2$, each power sequence satisfies the recurrence relation $x_{n+2}=x_{n+1}+x_n$, because both bases solve $t^2=t+1$. Their sum starts at $2,1$, so uniqueness of a recursively defined sequence proves that it is the Lucas number sequence. Alternatively, diagonalize the companion matrix $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ and use $(1,2{)}^T=(\phi ,1{)}^T+(\psi ,1{)}^T$. The formula explains the exponential growth governed by the golden ratio and the alternating decaying correction ${\psi }^n$.

Compute a nonnegative integer power $A^n$ by repeated squaring. If $n=2k$, use $A^n=(A^k{)}^2$; if $n=2k+1$, use $A^n=A(A^k{)}^2$. This needs $O(\log n)$ matrix multiplications and permits fast evaluation of fixed-order linear recurrences via a companion matrix. It is distinct from computing the matrix exponential $e^A$.

Let $A$ be a companion matrix of a monic irreducible polynomial $f\in F[x]$ of degree $n$. Form the $N$-by-$N$ block matrix $B$ with $A$ on its diagonal, $I_n$ immediately above the diagonal, and zero elsewhere. If the field characteristic is $p>0$, write $f(x)=h(x^q)$ with $q=p^r$ maximal, so that $h^{\prime }\ne 0$; in characteristic zero take $q=1$ and $h=f$. ThenThus a separable polynomial gives $m_B=f^N$, but an irreducible polynomial with zero formal derivative can give a smaller exponent. For example, over the rational function field ${\mathbb{F}}_2(t)$, the irreducible polynomial $f(x)=x^2-t$ has $q=2$, so a two-block chain still has minimal polynomial $f$.

To prove the formula, write $B=D+K$, where $D$ has diagonal blocks $A$ and $K$ is the block shift. These are commuting operators, and $K^j$ vanishes exactly when $j\ge N$. The binomial theorem in positive field characteristic gives $B^q=D^q+K^q$. Expanding $h(D^q+K^q)$ gives $f(B)=K^{q}H$, with $H$ commuting with $K$. The diagonal blocks of $H$ are $h^{\prime }(A^q)$, which are invertible by Bézout's identity for polynomials, since $h$ is irreducible with nonzero formal derivative and $h(A^q)=0$. Therefore $f(B{)}^s=K^{qs}{H}^s$ vanishes exactly when $qs\ge N$. Finally, the block upper triangular matrix determinant gives the displayed characteristic polynomial, while the Cayley-Hamilton theorem and irreducibility force the minimal polynomial to be a power of $f$.

The minimal polynomial $m_T$ is the unique monic polynomial of least degree with $m_T(T)=0$. Existence follows from a linear dependence among powers of $T$ in the finite-dimensional vector space $\mathrm{End}(V)$; polynomial division proves uniqueness and that it divides every annihilating polynomial. The characteristic polynomial is ${\chi }_T(t)=\det (tI-[T{]}_{\mathcal{B}})$, independent of basis because a change of basis conjugates the matrix.

WriteIn the cyclic basis, the companion matrix isFor $q(t)=t^n+a_{n-1}{t}^{n-1}+\cdots +a_0$, the displayed vector relation gives $q(T)v=0$. Polynomial evaluation commutes with $T$, so $q(T)T^{j}v=T^{j}q(T)v=0$ for every basis vector. Thus $q(T)=0$.

No nonzero polynomial of degree below $n$ can annihilate $T$, since applying it to the cyclic vector $v$ would contradict independence of $v,Tv,\dots ,T^{n-1}v$. Hence $m_T=q$. Finally, direct expansion of $\det (tI-C)$, or induction along the last column, gives ${\chi }_T(t)=t^n+a_{n-1}{t}^{n-1}+\cdots +a_0=q(t)$. ThereforeThe argument computes the determinant and annihilator directly and does not invoke the Cayley-Hamilton theorem.

Since $v$ is a cyclic vector and $V\ne 0$, $v\ne 0$. Finite dimension of a vector space forces a first dependence in the sequence $v,Tv,T^{2}v,\dots$. Let $k\ge 1$ be the smallest index with $T^{k}v$ in the linear span of its predecessors. Thenis linearly independent. Its linear span $W$ is invariant under $T$: all but the last basis candidate map to the next, and the last maps to $T^{k}v\in W$. Induction therefore puts every $T^{j}v$ in $W$. Cyclicity gives $W=V$, so $B$ is a basis and $k=n$.

WriteThe matrix of $T$ in this basis is the companion matrixFor $p(t)=t^n+a_{n-1}{t}^{n-1}+\cdots +a_0$, the defining relation says $p(T)v=0$. Since $p(T)$ commutes with $T$, it also annihilates every $T^{j}v$ in $B$, hence $p(T)=0$. No nonzero polynomial of degree less than $n$ can annihilate $v$, because that would contradict linear independence of $B$. Thus $m_T=p$.

Finally the characteristic polynomial of a companion matrix is $p$, by direct determinant expansion. Explicitly, expansion along the first row of $tI-C$ gives the recurrencestarting from $D_1=t+a_0$. It yields $D_n=t^n+a_{n-1}{t}^{n-1}+\cdots +a_0$. ConsequentlyThis proves that a cyclic operator has equal minimal and characteristic polynomials by the cyclic basis and a direct determinant calculation, with no appeal to the Cayley-Hamilton theorem.

For $d(X)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_0$, the determinant of its companion matrix is $(-1{)}^n{a}_0$. ThereforeThus invertibility is readable from the constant coefficient, with no factorization or elimination.

An $R$-module isomorphism $T:V_{\alpha }\to V_{\beta }$ is a $K$-linear isomorphism satisfying $T\alpha =\beta T$, by applying it to multiplication by $X$. Conversely that identity implies $Tf(\alpha )=f(\beta )T$ for every polynomial, so a similarity is an $R$-module isomorphism.

The cyclic decomposition theorem over the principal ideal domain $R=K[X]$ states that any finitely generated module iswith nonunit monic invariant factors, uniquely determined, and free rank $r$ uniquely determined. A finite-dimensional $K$-space has $r=0$. In each cyclic summand the basis $1,X,\dots ,X^{\mathrm{deg}{d}_i-1}$ makes multiplication by $X$ the companion matrix of $d_i$. Their block diagonal sum is the rational canonical form.

Here the two polynomials are already in divisibility order. With the companion convention having ones below the diagonal,Integer coefficients are interpreted in $K$, so this remains valid in characteristics two and three.

In the cyclic case there is one companion block $C(d)$. Its defining polynomial is both characteristic and minimal: the vector represented by $1$ is cyclic and a polynomial annihilates it exactly when divisible by $d$. Thus the minimal polynomial is read directly from that block.

Give $V$ a $k[t]$-module structure by $t\cdot v=\alpha v$. A finite vector space basis generates it as a module. It is a torsion module: the Cayley-Hamilton theorem gives a nonzero polynomial annihilating all of $V$. Since $k[t]$ is a Euclidean domain, cyclic decomposition giveswith monic nonconstant invariant factors of a linear operator $f_j$ and no free summand. On $k[t]/(f_j)$, use the basis $1,t,\dots ,t^{\mathrm{deg}{f}_j-1}$. Multiplication by $t$ then has the companion matrix $C(f_j)$, because the relation $f_j(t)=0$ expresses the last power in terms of earlier ones. Concatenating these bases yieldsthe rational canonical form of $\alpha$. In particular, its minimal polynomial is $f_s$ and its characteristic polynomial is ${\prod }_j{f}_j$.

The first block is the companion matrix of $t-3$. The last block is the companion matrix of $f(t)=t^3-3t^2+9t-27=(t-3)(t^2+9)$. Since $t-3$ divides $f$, these are the ordered invariant factors of a linear operator. ThusThe minimal polynomial is the largest invariant factor, and the characteristic polynomial is their product.

The displayed matrix is the transpose convention for a companion matrix. Expanding $\det (xI-A)$ along its last row givesIndeed, the last entry contributes $(x+{\alpha }_{n-1})x^{n-1}$ and the entry in column $j<n$ contributes ${\alpha }_{j-1}{x}^{j-1}$; the cofactor signs cancel those from the superdiagonal entries $-1$. ConsequentlyThe Cayley-Hamilton theorem gives $f(A)=0$, so $m_T$ divides $f$. To exclude a smaller minimal polynomial, let $e_1,\dots ,e_n$ be the standard basis. The first $n-1$ rows of $A$ showIf ${\sum }_{j=0}^{n-1}{c}_j{A}^j=0$, multiplying on the left by $e_1^{\mathsf{T}}$ gives ${\sum }_j{c}_j{e}_{j+1}^{\mathsf{T}}=0$, so every coefficient is zero. No nonzero polynomial of degree below $n$ vanishes at $A$. Since $f$ and $m_T$ are monic polynomials,

Put $\nu =k/\delta$ and use the discrete Fourier transform on the infinite grid. A spatial Fourier mode $e^{i(j\theta +\ell \varphi )}$ has time coefficient satisfyingIts amplification polynomial of a multilevel finite difference scheme is ${\zeta }^2-2is\zeta -1$, with rootsFor $|s|<1$ they are distinct and have modulus one. Since $|s|\le 2\nu$, a fixed $0<\nu <1/2$ bounds their separation below by $2\sqrt{1-4{\nu }^2}$. Solving for the two mode amplitudes therefore bounds every power of the two-level companion matrix uniformly in frequency and step number. Parseval identity transfers this bound to the discrete L2 norm.

If $\nu >1/2$, an open set of frequencies around $(\pi /2,\pi /2)$ has $|s|>1$ and a root of modulus greater than one. Fourier data supported there grow exponentially. At $\nu =1/2$, the central frequency has the double root $i$, and the recurrence admits $v_n=(A+Bn)i^n$. Thus the root moduli being one do not suffice: a nontrivial Jordan block makes the two-level powers grow linearly. Although this exact frequency has measure zero on the infinite grid, the matrices depend continuously on frequency. For every step count, a neighborhood has powers nearly as large, so their essential supremum is still unbounded. Wave packets in those neighborhoods rule out a uniform stability of a numerical method estimate in the discrete L2 norm.

For arbitrary perturbations in both starting levels the sharp positive range is thereforeThe zero-step limiting recurrence is bounded but does not advance time. A specially filtered startup can suppress a repeated-root mode; that restriction does not establish stability of the full two-level scheme. This is the two-dimensional leapfrog stability threshold.

Use a spatial discrete Fourier mode $u_{k,j}^n=a_n{e}^{i(k\xi +j\eta )}$. Its recurrence and amplification polynomial of a multilevel finite difference scheme areThe polynomial roots are $G_{\pm }=is\pm \sqrt{1-s^2}$. For $|s|<1$ both have modulus one and are separated. Since $|\sin \xi +\sin \eta |\le 2$, a fixed $0<\mu <1/2$ bounds their separation below by $2\sqrt{1-4{\mu }^2}$. The two-level companion matrix is therefore diagonalizable with uniformly bounded eigenvector matrix and inverse. To see the uniform bound explicitly, write $V=\left(\begin{array}{cc}{G}_{+}& G_{-}\\ 1& 1\end{array}\right)$. Its determinant is $G_{+}-G_{-}$; all its entries have modulus one, and those of $V^{-1}$ are bounded by the reciprocal of the root separation. The companion matrix powers are $V\mathrm{diag}(G_{+}^n,G_{-}^n)V^{-1}$, bounded independently of frequency and step number. Parseval's identity converts this into a mesh-independent discrete $L^2$ bound for arbitrary perturbations at the two initial levels.

If $\mu >1/2$, choose $\xi =\eta =\pi /2$. Then $s=2\mu >1$, and one polynomial root has modulus $s+\sqrt{s^2-1}>1$. On periodic meshes with the number of points divisible by four, this is an actual grid mode, producing exponential linear instability.

At $\mu =1/2$ the same phases give $(G-i{)}^2$. The companion matrix is not a scalar matrix, so the double polynomial root has a nontrivial Jordan block. The solution $a_n=n{i}^n$ has bounded starting amplitudes but grows like $n$. On a fixed physical time interval $n$ is of order $1/k$, so no mesh-independent stability bound exists. Consequentlyis the stability interval under the standard two-level definition. Testing only polynomial root moduli would misleadingly include the endpoint. A special startup selecting the non-growing branch at that endpoint restricts the perturbations and does not establish stability of the full recurrence. This is the two-dimensional leapfrog stability threshold.

Fourier transform on the infinite spatial lattice giveswith polynomial roots $G_{\pm }=iA\pm \sqrt{1-A^2}$. When $|A|$ is uniformly less than one, the polynomial roots have modulus one and a uniform positive separation. Diagonalizing the companion matrix then bounds all its powers independently of $\theta$ and $n$. Parseval's identity proves stability in the discrete $L^2$ norm for arbitrary square-summable starting perturbations at both levels.

At $\mu =1/2$ the coefficients giveConsequently $\mu =1/2$ is stable.

At $\mu =3/2$,The growing polynomial root at this phase has modulusTo turn this into a Cauchy problem linear instability proof, rather than rely on a plane wave of infinite norm, choose a small interval around $\pi /3$ on which the growing polynomial root has modulus at least $1+\delta$. Choose an initial Fourier transform amplitude that is a nonzero square-integrable function supported there, and set the level-one amplitude equal to that polynomial root times the level-zero amplitude. The recurrence then multiplies by the same growing polynomial root at every step on the support. Parseval identity gives $\Vert u^n{\Vert }_2\ge (1+\delta {)}^n\Vert u^0{\Vert }_2$, whereas both initial norms are bounded independently of $h$. Real data can be obtained by adding the conjugate interval around $-\pi /3$. Since $n=T/(\mu h)$ tends to infinity at fixed $T$, $\mu =3/2$ is unstable.

The $n$ spanning vectors form a basis. WriteIn this cyclic basis the matrix is the companion matrixExpanding $\det (tI-C)$ along its last column givesFor example, the term containing $a_j$ has minor $t^j$ and the signs from the subdiagonal cancel the cofactor sign; the diagonal term supplies $t^n$. The defining relation says ${\chi }_T(T)x=0$. Every polynomial in $T$ commutes with $T$, soIt therefore vanishes on a basis, provingThis direct argument for a cyclic vector does not assume the Cayley-Hamilton theorem.

The structure theorem for finitely generated modules over a principal ideal domain applies in particular to a Euclidean domain $R$: every finitely generated module has an isomorphismwith each $d_i$ nonzero and a nonunit. The rank of a free module $r$ and the invariant factors of a finitely generated module $d_i$ are unique up to multiplication by units; empty sums are allowed. This is the classification theorem being used, without a proof of that theorem.

The rational canonical form theorem states that for a linear operator $T$ on a finite-dimensional vector space over any field $F$, there are unique monic nonconstant polynomials $p_1\mid \cdots \mid p_k$ such that some basis givesHere, for $p(t)=t^d+a_{d-1}{t}^{d-1}+\cdots +a_0$, the companion matrix has ones on its subdiagonal and last column $(-a_0,\dots ,-a_{d-1}{)}^T$. The empty matrix covers a zero-dimensional space. Two linear operators have matrix similarity exactly when they have the same invariant factors of a linear operator.

For the proof, make $V$ an $F[t]$-module by $t\cdot v=T(v)$. It is a finitely generated module, since a vector-space basis also generates it as a module. It is a torsion module: the powers of $T$ have linear dependence in the finite-dimensional space ${\mathrm{End}}_F(V)$, so some nonzero polynomial annihilates every vector. Because $F[t]$ is a Euclidean domain, the classification theorem givesThere is no free summand, since a nonzero free module over $F[t]$ is not a torsion module. Choose monic generators of the ideals. On $F[t]/(p_i)$, the classes of $1,t,\dots ,t^{d_i-1}$ form an $F$-basis by polynomial division. Multiplication by $t$ is exactly $C(p_i)$ in that basis, proving existence. Uniqueness in the classification theorem proves uniqueness of the rational canonical form. Finally, an $F[t]$-module isomorphism is precisely an invertible $F$-linear map intertwining the operators, establishing the assertion about matrix similarity. In particular the characteristic polynomial is ${\prod }_i{p}_i$ and the minimal polynomial is $p_k$ for nonzero $V$.

Make $F^n$ an $F[X]$-module by $Xv=Av$. It is finitely generated and torsion, so the structure theorem gives cyclic summands $F[X]/(d_i)$ with $d_1\mid \cdots \mid d_k$. In the power basis of each summand, multiplication by $X$ has the companion matrix of $d_i$. Their block diagonal sum is the rational canonical form, unique because the invariant factors are unique.

The structure theorem for finitely generated modules over a principal ideal domain applies because every Euclidean domain is a principal ideal domain. It says that a finitely generated $R$-module is isomorphic towhere the nonzero nonunits $d_i$ are unique up to multiplication by units. They are the invariant factors.

For $V_{\alpha }$, multiplication by $X$ is the linear map $\alpha$. Since $V$ is finite-dimensional over $F$, $V_{\alpha }$ is a finitely generated torsion module over the polynomial ring $F[X]$, so it has no free summand. Choosing each invariant factor $a_i$ to be monic givesThe basis $1,X,\dots ,X^{\mathrm{deg}{a}_i-1}$ of each cyclic summand makes multiplication by $X$ a companion matrix. Concatenating these bases therefore puts $\alpha$ in rational canonical form.

On $F[X]/(a_i)$, a polynomial annihilates multiplication by $X$ exactly when it is divisible by $a_i$. It follows that the minimal polynomial and characteristic polynomial areThe second identity follows blockwise from the characteristic polynomial of a companion matrix. Since every $a_i$ divides $a_k$, the product ${\chi }_{\alpha }$ annihilates every cyclic summand. Thus ${\chi }_{\alpha }(\alpha )=0$, which is the Cayley-Hamilton theorem.

For the displayed matrix, the given generators of $\ker \theta$ are the columns ofElementary row and column operations over $\mathbb{R}[X]$ give the Smith normal formConsequently the nonunit invariant factors areand, as a check,

For the standard basis vector $e_j$, matrix multiplication selects the $j$th column, soConsequentlyand the columns of $PM$ are $P{c}_1,\dots ,P{c}_n$.

Suppose first that $v,Av,\dots ,A^{n-1}v$ are linearly independent, and defineThen $S$ is invertible. The first $n-1$ columns of $AS$ are the last $n-1$ columns of $S$. By the Cayley-Hamilton theorem,This is exactly the last-column rule for the companion matrix $C$, so

Conversely, suppose $S^{-1}AS=C$, or $AS=SC$, and write the columns of $S$ as $s_1,\dots ,s_n$. Comparing the first $n-1$ columns givesHenceSince $S$ is invertible, its columns are linearly independent. Taking $v=s_1$ therefore makeslinearly independent. Thus $A$ is similar to $C$ exactly when it has the stated cyclic vector.