Skip to content

3.26 Companion matrix

Let \(V\) be a k-vs, let \(f:V\to V\) be k-linear map. Let \(v\in V\) consider the set \(\{v,f(v),f^{2}(v),...\}=\{f^{i}(v)\}_{i\geq 0}\)

Suppose \(\dim V=n<\infty\), then \(\{v,f(v),f^{2}(v),...,f^{n-1}\left(v\right),f^{n}\left(v\right)\}\) and length is \(n+1\), then it is linearly dependent

And for \(\{v,f(v),f^{2}(v),...,f^{n-1}\left(v\right)\}\) may be linearly independent or linearly dependent (depends on \(v\) and \(f\))

We know \(\deg \chi_f(x)=n,\chi_f(f)=0\) and \(\chi_{f}(x)=a_{0}+a_{1}x+...+a_{n-1}x^{n-1}+x^{n}\)

Then \(0=\chi_{f}(f)=a_{0}Id+a_{1}f+...+a_{n-1}f^{n-1}+f^{n}\)

\(\forall w\in V,0_{V}=a_{0}w+a_{1}f\left(w\right)+...+a_{n-1}f^{n-1}\left(w\right )+f^{n}\left(w\right)\)

Thus \(f^{n}(w)=-a_{0}w-a_{1}f\left(w\right)-...-a_{n-1}f^{n-1}\left(w\right)\)

Definition

Let \(\lang v\rang_f\) be the subspace spanned by \(\{v,f(v),f^{2}(v),...,f^{n-1}\left(v\right)\}\), we will call it the \(f\)-cyclic subspace generated by \(v\)​

It's clearly \(\dim\lang v\rang_{f}\leq n\) and if \(v\neq 0_V\), then \(1\leq\dim\langle v\rangle_{f}\leq n\)

Example

  1. If \(v=0_V\), then \(\lang v\rang_f=\{0_V\},\forall f\)​

  2. If \(f=Id_V\), then \(\{v,f(v),...,f^{n-1}\left(v\right)\}=\{v\}\), then \(\dim \lang v\rang _f=1\)​

  3. Let \(v\) be an eigenvector of \(f\) with eigenvalue \(\lambda\), then \(\{v,f(v),...,f^{n-1}\left(v\right)\}=\{v,\lambda v,...,\lambda^{n-1}v\}\)​

    Then \(\dim\lang v\rang_f=\dim \lang v\rang=1\)​

  4. Let \(f:\mathbb{R}^{2}\to\mathbb{R}^{2}:[f]_{E}= \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}\)​

    Then \(f(e_1)=0_V\) and \(f(e_2)=e_1+e_2\). Thus \(\langle e_{2}\rangle_{f}=\langle e_{2},f(e_{2})\rangle=\langle e_{2},e_{1}+e_{2} \rangle=\mathbb{R}^{2}\)​

Definition

A vector \(v\in V\) is an \(f\)-cyclic vector (or a cyclic vector for \(f\)) if \(\lang v\rang _f=V\)

\(V,\dim_{k}V=m,f:V\to V,v\in V\)

\(m_{f}(x),m_{f}(f)=0,\text{that is }m_{f}(f)(w)=0,\forall w\in V\)

\(m_{f,v}(x),\text{(it is the unique monic polynomial of minimal degree such that }m_{f,v}(f)(v)=0_{V}\text{)}\)

\(\text{So }m_{f,v}(x)\text{ divides }m_{f}(x),\text{ so }\deg m_{f,v}(x)\leq\deg m_{f}(x)\)

Remark: If \(m_{f,v}(x) = x^r + b_{r-1} x^{r-1} + \dots + b_1 x + b_0 \quad (r \leq \deg m_f(x))\)

Then \(0_V = m_{f,v}(f)(v) = f^r(v) + b_{r-1} f^{r-1} (v) + \dots + b_1 f(v) + b_0 v\)

So, \(\dim_k \langle v \rangle_f \leq r\)

Proposition

  1. \(\dim\lang v\rang_{f}=\deg m_{f,v}(x)\)​

  2. If \(\deg m_{f,v}(x)=r\), then \(\{v,f(v),...,f^{r-1}(v)\}\) is linearly independent. (Thus it is a basis of \(\lang v\rang_{f}\)​)

  3. If \(\lang v\rang_f\) is \(f\)-invariant and setting \(g=f|_{\lang v\rang_{f}}\), then \(m_g(x)=m_{f,v}(x)\)

Proof

(1) and (2)

Let \(p(x)\in k[x]\), \(\exists\) unique \(q(x),r(x)\in k[x]\) such that \(p(x)=m_{f,v}(x)q(x)+r(x)\) with \(r(x)=0\) or \(\deg r(x)<\deg m_{f,v}(x)\)

Given \(w\in \lang v\rang_f,\exists \gamma(x)\in k[x]:w=\gamma(f)(v)\)

This is because

We know that \(w\in\langle v,f(v),...,f^{n-1}\left(v\right)\rangle\), so \(\exists\alpha_{0},...,\alpha_{n-1}\in k:w=\alpha_{0}v+\alpha_{1}f\left(v\right)+ \cdots+\alpha_{n-1}f^{n-1}\left(v\right)=\left(\alpha_{0}Id+\alpha_{1}f+\cdots+\alpha _{n-1}f^{n-1}\right)\left(v\right)\)

Take \(\gamma(x)=\left(\alpha_{0}Id+\alpha_{1}f+\cdots+\alpha_{n-1}f^{n-1}\right)\)

Write: \(\gamma(x)=m_{f},v(x)q_{\gamma}(x)+r_{\gamma}(x)\) where \(r_\gamma(x)=0\) or \(\deg r_\gamma(x)<\deg m_{f,v}(x)=r\)

Thus \(w=\gamma(f)(v)=q_{\gamma}(f)(m_{f,v}(f)(v))+r_{\gamma}(f)(v)\)

Since \(m_{f,v}(f)(v)=0\), then \(w=r_\gamma(f)(v)\) is a linear combination of \(v,f(v),...,f^{r-1}(v)\)

Thus \(\lang v\rang_{f}=\lang v,f(v),...,f^{r-1}(v)\rang\)

Then we prove it's linearly independent

Suppose \(\exists c_0,...,c_{r-1}\in k:0_V=c_0v+c_1f(v)+...+c_{r-1}f^{r-1}(v)\)

Thus the polynomial \(c_0+c_1x+...+c_{r-1}x^{r-1}=t(x)\) is such that \(t(f)(v)=0_V\)

If \(c_0,...,c_{r-1}\) are not all \(0\), then \(\deg t(x)\leq r-1<r=\deg m_{f,v}(x)\), contradiction!

Thus \(c_0=...=c_{r-1}=0\), then \(\{v,f(v),...,f^{r-1}(v)\}\) is a basis of \(\lang v\rang_f\)

(3)

Since given \(w\in \lang v\rang_f\), then \(w=\alpha_{0}+\alpha_{1}f(v)+....+\alpha_{r-1}f^{r-1}(v)\)

Thus \(f(w)=f\left(\alpha_{0})+\alpha_{1}f^{2}(v\right)+....+\alpha_{r-1}f^{r}(v)\). We know \(f^r(v)\) is a linear combination of \(v,f(v),...,f^{r-1}(v)\)

Thus \(\lang v\rang_f\) is \(f\)-invariant.

Let \(g=f|_{\lang v\rang_{f}}\), NTP: \(m_g(x)\mid m_{f,v}(x)\) and \(m_{f,v}(x)\mid m_g(x)\)

For the first

We know \(m_{f,v}(f)(v)=0_{V}\), then \(m_{f,v}(g)(v)=0_{V}\). Also, \(m_{f,v}(f)(f(v))=f(m_{f,v}(f))=0_{V}\)

In fact \(\forall i\), then \(0_{V}=m_{f,v}(f)(f^{i}(v))=f^{i}(m_{f,v}(f)(v))\)

Thus \(m_{f,v}(f)(w)=0_{V}=m_{f,v}(g)(w),\forall w\in\langle v\rangle_{f}\). Thus \(m_{g}(x)\mid m_{f,v}(x)\)

For the second

It's easier to prove \(\deg m_{g}(x)=\deg m_{f,v}(x)=r\)​

Suppose \(\deg m_{g}(x)=s<r\), then \(\{v,f(v),...,f^{r-1}(v)\}\) is linear dependent

Then \(m_g(x)=\beta_0+\beta_1x+...+\beta_sx^s\), then \(m_g(g)(v)=0=\beta_0v+....+\beta_sf^s(v)\)

Since \(\deg m_g(x)=r\), then \(\beta_s\neq 0\), then \(f^s(v)\) is a linear combination of \(\{v,f(v),...,f^{s-1}(v)\}\)

Contradicts to \(\{v,f(v),...,f^{s-1}\left(v),f^{s}\left(v\right),\ldots,f^{r-1}(v\right)\}\) is linearly independent

Corollary

Suppose \(\exists v\in V:\lang v\rang_{f}=V\), then \(\chi_{f}(x)=m_{f}(x)\)

Proof

Since \(\langle v\rangle_{f}=V\) and by proposition, \(\deg m_{f,v}(x)=\dim\langle v\rangle_{f}=\dim V=\deg\chi_{f}(x)\)

And \(m_{f,v}(x)\mid m_f(x)\), \(m_f(x)\mid \chi_f(x)\), then \(m_{f,v}(x)\mid \chi_f(x)\).

But we know \(\deg m_{f,v}(x)=\deg \chi_f(x)\), then \(m_{f,v}(x)=\chi_{f}(x)=m_{f}(x)\)​

Example

\(f:\R^3\to \R^3\) such that for some basis \(\mathcal{B},[f]_{\mathcal{B}}= \begin{pmatrix} 2 & 0 & 0 \\ 1 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}\), recall

Then \(\chi_f(x)=(x-2)^2(x-3)\)

We know that \(f\) is not diagonalizable, then \(m_f(x)=(x-2)^2(x-3)=\chi_f(x)\)

\(\mathcal{B}=\{\underbrace{v_1}_{\in \ker(f-2Id)^2\setminus \ker(f-2Id)},\underbrace{v_2}_{=(f-2Id)(v_1)\in \ker (f-2Id)},\underbrace{v_3}_{\text{eigenvectors of eigenvalue }3}\}\)

\(m_{f,v_1}=(x-2)^2\) and \(\deg m_{f,v_1}(x)=2\), thus \(\lang v_1\rang_f\subsetneq V=\R^3\)

Let \(v=v_1+v_3\), then \(f(v)=f(v_{1})+f(v_{3})=f(v_{1})+3v_3\)

Since \(v_2=f(v_1)-2v_1\), then \(f(v_1)=2v_1+v_2\). Thus \(f(v)=2v_{1}+v_{2}+3v_{3}\)

\(f^{2}(v)=f(2v_{1}+v_{2}+3v_{3})=2f(v_{1})+f(v_{2})+3f(v_{3})=4v_{1}+4v_{2}+9v_{3}\)

Then \(v,f(v),f^2(v)\) are linearly independent. Thus \(\dim\lang v\rang_f=3\), then \(\lang v\rang_f=\R^3\)

Let \(\mathcal{B'}=\{v,f(v),f^{2}(v)\}\) is a basis of \(\R^{3}\), then \([f]_{\mathcal{B^{\prime}}}= \begin{pmatrix} 0 & 0 & 7 \\ 1 & 0 & -16 \\ 0 & 1 & 12 \end{pmatrix}\)

For the third column, \(f(f^2(v))=f^3(v)\)

Since \(v\) is an \(f\)-cyclic vector, then \(m_{f,v}(x)=\chi_{f}(x)=x^{3}-7x^{2}+16x-12\)

Then \(f^3(v)=7f^2(v)-16f(v)+12v\)

Summary

If \(\exists v\in V:\lang v\rang_f=V\), then \(\chi_{f}(x)=m_{f}(x)=m_{f,v}(x)\), then \(\mathcal{B'}=\{v,f(v),...,f^{n-1}(v)\}\) is a basis of \(V\)

Thus \([f]_{\mathcal{B^{\prime}}}=\)image​ where \(\chi_f(x)=x^n+a_{n-1}x^{n-1}+...+a_1x+a_0\)

This matrix is called the companion matrix of \(\chi_f(x)\) and written as \([f]_{\mathcal{B'}}=C_f\)​