# Rank of composition of linear maps

#### mathmari

##### Well-known member
MHB Site Helper
Hey!!

Question 1:
Let $C$ be a $\mathbb{R}$-vector space, $1\leq n\in \mathbb{N}$ and let $\phi_1, \ldots , \phi_n:V\rightarrow V$ be linear maps.
I have shown by induction that $\phi_1\circ \ldots \circ \phi_n$ is then also a linear map.
I want to show now by induction that if $V$ is finite then $\text{Rank}(\phi_1\circ \ldots \circ \phi_n)\leq \min \{\text{Rank}(\phi_i)\mid 1\leq i\leq n\}$.

Base Case : For $n=1$ we have that $\text{Rank}(\phi_1)\leq \min \{\text{Rang}(\phi_1)\}$, so the equality holds.
Inductive Hypothesis : We suppose that it holds for $n=m$, so $\text{Rank}(\phi_1\circ \ldots \circ \phi_m)\leq \min \{\text{Rank}(\phi_i)\mid 1\leq i\leq m\}$. (IV)
Inductive Step : We want to show that it holds for $n=m+1$, i.e. that $\text{Rank}(\phi_1\circ \ldots \circ \phi_m\circ \phi_{m+1})\leq \min \{\text{Rank}(\phi_i)\mid 1\leq i\leq m+1\}$.
Does it hold in general that $\text{Im}(f\circ g)\subseteq \text{Im}(f)$ and $\text{Im}(f\circ g)\subseteq \text{Im}(g)$ and so we get $\text{Rank}(f\circ g)\leq \text{Rank}(f)$ and $\text{Rank}(f\circ g)\leq \text{Rank}(g)$ ?

Last edited:

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Does it hold in general that $\text{Im}(f\circ g)\subseteq \text{Im}(f)$ and $\text{Im}(f\circ g)\subseteq \text{Im}(g)$ and so we get $\text{Rank}(f\circ g)\leq \text{Rank}(f)$ and $\text{Rank}(f\circ g)\leq \text{Rank}(g)$ ?
Hey mathmari !!

I'm afraid not.

Consider $f:v\mapsto e_1$ and $g:v\mapsto e_2$. Then $\text{Im}(f\circ g)\not\subseteq \text{Im}(g)$.

#### mathmari

##### Well-known member
MHB Site Helper
I'm afraid not.

Consider $f:v\mapsto e_1$ and $g:v\mapsto e_2$. Then $\text{Im}(f\circ g)\not\subseteq \text{Im}(g)$.
Ah ok.. But how can we continue then the inductive step?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Ah ok.. But how can we continue then the inductive step?
The rank of a function with a specific domain is the number of independent vectors in the image.
And the number of independent vectors in the image is at most the number of independent vectors in the domain.

#### mathmari

##### Well-known member
MHB Site Helper
The rank of a function with a specific domain is the number of independent vectors in the image.
And the number of independent vectors in the image is at most the number of independent vectors in the domain.
But how do we use that? I got stuck right now.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
But how do we use that? I got stuck right now.
Suppose $\operatorname{Rank}(f\circ g)>\operatorname{Rank}(g)$.
Then there must be more independent vectors in $(f\circ g)(V)$ than in $g(V)$.
But there can only be at most as many independent vectors in $f(g(V))$ as there are in $g(V)$.
Therefore $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(g)$.

#### mathmari

##### Well-known member
MHB Site Helper
Suppose $\operatorname{Rank}(f\circ g)>\operatorname{Rank}(g)$.
Then there must be more independent vectors in $(f\circ g)(V)$ than in $g(V)$.
But there can only be at most as many independent vectors in $f(g(V))$ as there are in $g(V)$.
Therefore $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(g)$.
Ahh ok

And in general it holds that $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(f)$.

So we have that $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(f)$ and $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(g)$ and then we take the minimum?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
And in general it holds that $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(f)$.

So we have that $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(f)$ and $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(g)$ and then we take the minimum?
Yep.