# Show that these elements are linearly independent

#### mathmari

##### Well-known member
MHB Site Helper
Hey!! Let $1\leq n\in \mathbb{N}$, let $\mathbb{K}$ be a field, $V$ a $\mathbb{K}$-vector space with $\dim_{\mathbb{K}}V=n$ and let $\phi:V\rightarrow V$ be linear.

- Let $0\neq v\in V$ and $1\leq m\in \mathbb{N}$, such that $\phi^{m-1}(v)\neq 0=\phi^m(v)$. Show that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v)$ are linearly independent.

Hint : Use induction for $m$ and for the case $m\geq 2$ consider $w=\phi (v)$.

- Let $v,m$ as above. Let $B=(b_1, \ldots , b_n)$ be a basis of $V$, with $b_i=\phi^{i-1}(v)$ for all $1\leq i\leq m$. Describe the first $m-1$ columns of $M_B(\phi)$.

I have done the following:

- Base case: If $m=1$ the we have the element $\phi^0(v)=v$. This element is linearly independent.

Inductive hypothesis: We assume that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v)$ are linearly independent. (IH)

Inductive step: We want to show that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v), \phi^m(v)$ is linearly independent.

\begin{align*}&\lambda_0\phi^0(v)+\lambda_1\phi (v)+ \ldots +\lambda_{m-1}\phi^{m-1}(v)+\lambda_m \phi^m(v)=0 \\ & \Rightarrow \lambda_m \phi^m(v)=-\lambda_0\phi^0(v)-\lambda_1\phi (v)- \ldots -\lambda_{m-1}\phi^{m-1}(v)\end{align*}

We know that the elements of the right side are linearly independent. How can we use that information
here? Could you give me a hint?

Last edited:
• Klaas van Aarsen

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hey!! Let $1\leq n\in \mathbb{N}$, let $\mathbb{K}$ be a field, $V$ a $\mathbb{K}$-vector space with $\dim_{\mathbb{K}}V=n$ and let $\phi:V\rightarrow V$ be linear.

- Let $0\leq v\in V$ and $1\leq m\in \mathbb{N}$, such that $\phi^{m-1}(v)\neq 0=\phi^m(v)$. Show that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v)$ are linearly independent.

Hint : Use induction for $m$ and for the case $m\geq 2$ consider $w=\phi (v)$.

- Let $v,m$ as above. Let $B=(b_1, \ldots , b_n)$ be a basis of $V$, with $b_i=\phi^{i-1}(v)$ for all $1\leq i\leq m$. Describe the first $m-1$ columns of $M_B(\phi)$.

I have done the following:

- Base case: If $m=1$ the we have the element $\phi^0(v)=v$. This element is linearly independent.

Inductive hypothesis: We assume that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v)$ are linearly independent. (IH)

Inductive step: We want to show that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v), \phi^m(v)$ is linearly independent.

\begin{align*}&\lambda_0\phi^0(v)+\lambda_1\phi (v)+ \ldots +\lambda_{m-1}\phi^{m-1}(v)+\lambda_m \phi^m(v)=0 \\ & \Rightarrow \lambda_m \phi^m(v)=-\lambda_0\phi^0(v)-\lambda_1\phi (v)- \ldots -\lambda_{m-1}\phi^{m-1}(v)\end{align*}

We know that the elements of the right side are linearly independent. How can we use that information
here? Could you give me a hint?
Hey mathmari !!

I believe the inductive hypothesis should be:

For some $m\ge 1$ we assume that for any $v\in V$ such that $\phi^{m-1}(v)\neq 0=\phi^m(v)$ we have that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v)$ are linearly independent (IH).

Then we have to prove in the inductive step that for any $v\in V$ such that $\phi^{m}(v)\neq 0=\phi^{m+1}(v)$ we have that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m}(v)$ are linearly independent.

Now consider $w=\phi(v)$. Last edited:
• mathmari

#### Klaas van Aarsen

##### MHB Seeker
Staff member
We have $\phi^0(w)=\phi^1(v),\ldots,\phi^{m-1}(w)=\phi^{m}(v)\ne 0,\phi^m(w)=\phi^{m+1}(v)=0$.
According to the inductive hypothesis this means that $\phi^1(v),\ldots, \phi^{m}(v)$ are independent.
What is left to prove, is that if we add $v$ to the set, that it is still independent, yes? So suppose the resulting set in not independent.
Then it must be possible to write $v$ as a linear combination of $\phi^1(v),\ldots, \phi^{m}(v)$.
Apply $\phi$ on both sides. Can we reach a contradiction? • mathmari

#### mathmari

##### Well-known member
MHB Site Helper
We have $\phi^0(w)=\phi^1(v),\ldots,\phi^{m-1}(w)=\phi^{m}(v)\ne 0,\phi^m(w)=\phi^{m+1}(v)=0$.
According to the inductive hypothesis this means that $\phi^1(v),\ldots, \phi^{m}(v)$ are independent.
From the inductive hypothesis we have that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v)$ are independent, right? How do we get that $\phi^1(v),\ldots, \phi^{m}(v)$ are independent? What is left to prove, is that if we add $v$ to the set, that it is still independent, yes? I got stuck right now. Why do we check if the set is still independent when we add the vector $v$ ? Because above we don't have $\phi^0(v)$? #### Klaas van Aarsen

##### MHB Seeker
Staff member
From the inductive hypothesis we have that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v)$ are independent, right? How do we get that $\phi^1(v),\ldots, \phi^{m}(v)$ are independent?
Let $w=\phi(v)$ in the inductive step. Then we have $\phi^0(w)=w, \phi (w), \ldots ,\phi^{m-1}(w)\ne 0,\phi^m(w)=0$ yes?
Can we apply the IH from post #2 to that? I got stuck right now. Why do we check if the set is still independent when we add the vector $v$ ? Because above we don't have $\phi^0(v)$?
Let's apply IH from post #2 to $w=\phi(v)$ first and see what comes out of it. Then we'll get back to this. Last edited:
• mathmari

#### mathmari

##### Well-known member
MHB Site Helper
So do we have the following?

Bas Case: If $m=1$ then we have one element $\phi^0(v)=v$. This element is linearnly independent.

Inductive Hypothesis: For a $m\ge 1$ we assume that for a $v\in V$ such that $\phi^{m-1}(v)\neq 0=\phi^m(v)$ we have that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m-1}(v)$ are linearly independent. (IH)

Inductive Step: We want to show that for $v\in V$ with $\phi^{m}(v)\neq 0=\phi^{m+1}(v)$ it holds that $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m}(v)$ are linearly independent.
We consider $w=\phi(v)$.
Then we have that $\phi^0(w)=w, \phi (w), \ldots ,\phi^{m-1}(w)\ne 0,\phi^m(w)=0$.
From (IH) we have that $\phi^0(w), \phi (w), \ldots ,\phi^{m-1}(w)$ are lineanrlyindependent. Since $\phi^0(w)=\phi^1(v),\ldots,\phi^{m-1}(w)=\phi^{m}(v)$, it follows that $\phi^1(v),\ldots,\phi^{m}(v)$ are linearly independent.
We check if the set remains linearly independent even if we add $v$ to the set.
We assume that this set is linearly dependent
Then we can write $v$ as a linear combination of $\phi^1(v),\ldots, \phi^{m}(v)$.
We apply $\phi$ at both sides.
\begin{align*}&v=\lambda_1\phi^1(v)+\ldots+\lambda_{m-1}\phi^{m-1}(v)+\lambda_m \phi^{m}(v) \\ & \Rightarrow \phi (v)=\phi \left (\lambda_1\phi^1(v)+\ldots+\lambda_{m-1}\phi^{m-1}(v)+\lambda_m \phi^{m}(v)\right ) \\ & \Rightarrow \phi (v)=\lambda_1\phi^2(v)+\ldots+\lambda_{m-1}\phi^{m}(v)+\lambda_m \phi^{m+1}(v) \\ & \Rightarrow \phi (v)=\lambda_1\phi^2(v)+\ldots+\lambda_{m-1}\phi^{m}(v)+\lambda_m \cdot 0 \\ & \Rightarrow \phi (v)=\lambda_1\phi^2(v)+\ldots+\lambda_{m-1}\phi^{m}(v) \\ & \Rightarrow -\phi (v)+\lambda_1\phi^2(v)+\ldots+\lambda_{m-1}\phi^{m}(v)=0 \\ & \Rightarrow -\phi^1 (v)+\lambda_1\phi^2(v)+\ldots+\lambda_{m-1}\phi^{m}(v)=0\end{align*}
This means that $\phi^1(v),\ldots,\phi^{m}(v)$ are linearly dependent, since not all coefficients are zero.
A contradiction. Therefore $\phi^0(v)=v, \phi (v), \ldots ,\phi^{m}(v)$ are linearly independent.

Is everything correct? Could you give me also a hint for the second question? It must hold that $\phi (b_i)=b_i\Rightarrow \phi^i(v)=b_i$, or not?

Last edited:

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Is everything correct?

Could you give me also a hint for the second question?
Yep. The columns of the matrix of $\phi$ with respect to $B$ are the images of the basis vectors with respect to $B$ aren't they?
The first basis vector is $b_1$, which is represented by $\begin{pmatrix}1\\0\\\vdots\\0\end{pmatrix}$.
And its image (assuming $m\ge 2$) is $b_2$, which is represented by $\begin{pmatrix}0\\1\\0\\\vdots\\0\end{pmatrix}$, which is also the first column of the matrix then, isn't it? • mathmari

#### mathmari

##### Well-known member
MHB Site Helper
The columns of the matrix of $\phi$ with respect to $B$ are the images of the basis vectors with respect to $B$ aren't they?
The first basis vector is $b_1$, which is represented by $\begin{pmatrix}1\\0\\\vdots\\0\end{pmatrix}$.
And its image (assuming $m\ge 2$) is $b_2$, which is represented by $\begin{pmatrix}0\\1\\0\\\vdots\\0\end{pmatrix}$, which is also the first column of the matrix then, isn't it? So is the $i$-th column of the matrix the vector $e_{i+1}$ ? #### Klaas van Aarsen

##### MHB Seeker
Staff member
So is the $i$-th column of the matrix the vector $e_{i+1}$ ?
Yep. Up to column $m-1$ that is. We don't know what the remaining columns are. • mathmari

#### mathmari

##### Well-known member
MHB Site Helper
Yep. Up to column $m-1$ that is. We don't know what the remaining columns are. Do we know that this holds till the column $m-1$ because we only know that the $\phi^i$'s for $0\leq i\leq m-1$ are linearly independent? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Do we know that this holds till the column $m-1$ because we only know that the $\phi^i$'s for $0\leq i\leq m-1$ are linearly independent?
It's not about linear independence is it?
Just that we only know $\phi^i(b_1)=\phi^i(v)$ up to $i=m-1$. #### mathmari

##### Well-known member
MHB Site Helper
It's not about linear independence is it?
Just that we only know $\phi^i(b_1)=\phi^i(v)$ up to $i=m-1$. How do we get $\phi^i(b_1)=\phi^i(v)$ ?
We have that $b_i=\phi^{i-1}(v) \Rightarrow \phi (b_i)=\phi^{i}(v)$, or not? #### Klaas van Aarsen

##### MHB Seeker
Staff member
How do we get $\phi^i(b_1)=\phi^i(v)$ ?
We have that $b_i=\phi^{i-1}(v) \Rightarrow \phi (b_i)=\phi^{i}(v)$, or not?
I should have written $\phi^i(b_1)=\phi^{i-1}(v)$. 