# Some really tricky concepts that need to be cleared up in linear algebra

Suppose the matrix $A \in M_n(\mathbb{F})$ (the set of $n \times n$ matrices with coefficients in $\mathbb{F}[x]$), and the vector $v \in \mathbb{F}^n$. Now let $k>0$ be the smallest integer such that the set of vectors $\{v,Av,A^2v,\ldots,A^kv\}$ is linearly dependent.

Let us now define $$V= \operatorname{Span}(\{v,Av,\ldots,A^{k-1}v\}).$$ How do we show that this set of vectors spanning $V$ is a basis $\mathcal{B}$? Well, to be a basis for some vector space, we require that the set of vectors span that vector space, which in this case, they do and that the set of vectors be linearly independent. This is where one of my difficulties arises: how is it that $\{v,Av,\ldots,A^{k-1}v\}$ is linearly independent, while $\{v,Av,\ldots,A^kv\}$ is not?

Next, suppose we let the transformation $T:V\rightarrow V$ be induced by multiplication by $A$, i.e. $T(w)= Aw$ for $w \in V$. How exactly do we find the coordinate matrix $[T]_{\mathcal{B}}$? I don't quite remember how to do this. I would guess that it would be something like this, but I'm not sure:
$$[w|Aw|\cdots|A^{k-1}w]_{\mathcal{B}}.$$ Where do I go from here?

Finally, I know that the annihilator of $v$ w.r.t. $A$ given as the set
$$\{g \in \mathbb{F}[x]: g(A)(v)=0\},$$ is an ideal in $\mathbb{F}[x]$. But if I define the annihilator of the vector space $V$ w.r.t. $A$ as
$$\{g \in \mathbb{F}[x]: g(A)(w)=0 \forall w \in V\},$$ wouldn't both annihilators be the same? If so, how? I would really appreciate some help here.

-
@joriki: Never mind: I misread it. – Brian M. Scott Sep 27 '12 at 0:26
@Sachin: $\{v,Av,\dotsc,A^{k−1}v\}$ is linearly independent because if it were linearly dependent $k$ wouldn't be the smallest integer such that $\{v,Av,\dotsc,A^kv\}$ is linearly dependent. Likewise, $\{v,Av,\dotsc,A^kv\}$ isn't linearly independent because if it were, $k$ wouldn't be the smallest integer such that $\{v,Av,\dotsc,A^kv\}$ is linearly dependent. – joriki Sep 27 '12 at 0:29
You should either require $v\ne 0$ or only expect $k$ to be $\ge0$ (instead of $>0$). Otherwise it might happen that $\{v, \ldots A^{k-1}v\}=\{0\}$ is linearly dependant! – Hagen von Eitzen Sep 30 '12 at 13:31

We have that $\mathcal{B}=\{v,Av,\ldots,A^{k-1}v\}$. Set $v_{i+1}=A^iv\;\;\;\forall i \in \{0,1,\ldots,k-1\}$. So we have $Av_i=v_{i+1}\;\;\forall i=1,2,\ldots k-1$

By definition $[T]_{\mathcal{B}}=(a_{i,j})$ is the matrix with

\begin{split} T(v_1)&=a_{1,1}v_1+a_{2,1}v_2+\ldots+a_{k,1}v_k\\ T(v_2)&=a_{1,2}v_1+a_{2,2}v_2+\ldots+a_{k,2}v_k\\ \vdots\;\;&\;\;\;\;\;\;\;\;\vdots\\ T(v_k)&=a_{1,k}v_1+a_{2,k}v_2+\ldots+a_{k,k}v_k\\ \end{split}

Since $T(v_i)=Av_i=v_{i+1}\;\;\forall i=1,2,\ldots k-1$ we deduce that the first k-1 columns of $[T]_{\mathcal{B}}$ are the vectors $e_{i+1}= \begin{pmatrix} 0 \\ \vdots \\ 1 \\ \vdots \\ 0 \end{pmatrix}\ ,$ the $1$ being in the ${i+1}^{th}$ position, respectively. The last column of $[T]_{\mathcal{B}}$ is calculated by the definition of $k$. By the definition of $k$ we have that

$T(v_{k})=A^kv=c_1v+c_2Av+\ldots+c_kA^{k-1}v=c_1v_1+c_2v_2+\ldots+c_kv_k$

for some $c_i\in \mathbb{F}$, so the last column of $[T]_{\mathcal{B}}$ will be $\begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_k \end{pmatrix}\ .$

For your third question the answer is yes the two annihilators will be the same since:

i) if $h\in \{g \in \mathbb{F}[x]: g(A)(w)=0 \forall w \in V\} \Longrightarrow h(A)(v)=0$

so

$$h \in \{g \in \mathbb{F}[x]: g(A)(v)=0\} \ .$$

ii) if $h \in \{g \in \mathbb{F}[x]: g(A)(v)=0\} \Longrightarrow h(A)(v)=0$.

Observe that $h(A)(A^iv)=(hx^i)(A)(v)=(x^ih)(A)(v)=A^i(h(A)(v))=0\;\;\forall\; i \in \mathbb{N}$.

Using the fact that $V= Span(\{v,Av,…,A^{k-1}v\})$ we deduce

$$h \in \{g \in \mathbb{F}[x]: g(A)(v)=0\} \ .$$

-
Wouldn't the $c_i \in \mathbb{F}$? – Libertron Sep 29 '12 at 21:50
@Sachin: Yes $c_i\in \mathbb{F}$. I corrected that. Thanks. – P.. Sep 30 '12 at 6:36
1. Since $F^n$ has dimension $n$, any $n+1$ vectors are linearly dependent, so are $v,Av,A^2v,\dots,A^nv$. So, there must exist a least integer $k$ as it is said above. So the answer on your first question is: by def. of $k$.

2. $\mathcal B$ denotes the basis $\langle v,Av,..A^{k-1}v\rangle$ (for a tuple of vectors being a basis in the space they span is equivalent to being linearly independent). Then the columns of $[A]_{\mathcal B}$ are the $A$ images of the basis elements, in the given order, the images written into coordinates according to $\mathcal B$.

-

For your second question, you know that $v, Av, \dots, A^k v$ are linearly dependent, so that there are $c_0, c_1, \dots, c_k \in \mathbb{F}$ such that $c_0 v + c_1 Av + \cdots + c_k A^k v = 0$. Now $c_k \neq 0$ (otherwise $v, Av, \dots, A^{k-1} v$ would be linearly dependent), so we may divide the equation by $c_k$ and therefore assume $c_k = 1$.

Let's describe your basis as $w_1 = v, w_2 = Av, \dots, w_k = A^{k-1} v$. Then we have, for $1 \leq i \leq k-1$, $$A(w_i) = A(A^{i-1}(v)) = A^i(v) = w_{i+1}.$$ For $i = k$, we must use the linear dependency: \begin{align*} A(w_k) = A(A^{k-1}(v)) = A^k(v) & = -c_0 v - c_1 Av - \dots - c_{k-1} A^{k-1}v \\ & = -c_0 w_1 - c_1 w_2 - \cdots - c_{k-1} w_k. \end{align*}

For your last question, notice that the annihilator of the vector $v = 0$ wrt $A$ is always $\langle x \rangle$, the ideal generated by $x$. But the annihilator of $V$ wrt $A$ is never $\langle x \rangle$ unless $A = 0$ (edit: or $V = 0$).

Edit: As pambos pointed out, the question about annihilators refers to $v$ and $V$ as defined earlier. In that case, the annihilator of $v$ is the annihilator of $V$. If you assume that $p(x)$ is in the annihilator of $v$, i.e. $p(A)(v) = 0$, then it follows that $p(A)(A^i v) = A^i(p(A)(v)) = 0$, so each $p(A)$ annihilates each $A^i v$ and thus annihilates $V$.

-
@micheal can you please explain, in what ring are we considering the ideal? – Phani Raj Sep 29 '12 at 19:30
@PhaniRaj: In the ring $\mathbb{F}[x]$ of polynomials in one variable with coefficients in the given field $\mathbb{F}$. – Michael Joyce Sep 29 '12 at 20:12
@Pambos: No, $v = 0$ is in every vector space $V$, not just the zero vector space. The annihilator of a single vector wrt a linear transformation is a different concept than the annihilator of a vector space wrt a linear transformation. (Perhaps what you are getting at is that the annihilator of a vector $v$ is the same as the annihilator of the vector space $\text{Span}(v)$, but not every vector space is the span of a single vector!) – Michael Joyce Sep 29 '12 at 20:44
@MichaelJoyce: Correct, but in our case $V=\operatorname{Span}(\{v,Av,\ldots\})$ and the question is if the annihilator of $v$ is the same as the annihilator of $V$. – P.. Sep 29 '12 at 21:02
@Pambos: Oh yes, I interpreted the third question independently of the first two, but of course your interpretation is much more sensible! – Michael Joyce Sep 29 '12 at 21:06