# 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

##### 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:

#### 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

##### 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

##### 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

##### 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

##### 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)$.