Welcome to our community

Be a part of something great, join today!

Rank of composition of linear maps

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
Hey!! :giggle:

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)$ ?

:unsure:
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,591
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. (Shake)

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
Apr 14, 2013
4,713
I'm afraid not. (Shake)

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? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,591
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
Apr 14, 2013
4,713
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. :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,591
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)$.
Contradiction.
Therefore $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(g)$. 🤔
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,713
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)$.
Contradiction.
Therefore $\operatorname{Rank}(f\circ g)\le\operatorname{Rank}(g)$. 🤔
Ahh ok (Malthe)

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? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,591
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. (Nod)