What values can rank(A) and rank(A^2) have? Let $n$ be a positive integer. Determine the set of ordered pairs {$(rank(A),rank(A^2)) : A \in M_{n \times n}(\mathbb{F}$)}
My prof gave the hint that we can use Sylvester's rank inequality: if A is an m × n matrix and B is n × k, then $Rank(A) + Rank(B) - n \leq Rank(AB)$.
I have found the inequalities $rank(A) \geq rank(A^2)$ and $rank(A) \leq (Rank(A^2) + n)/2$. Letting $A^2 = 0$ we get that $rank(A) \leq n/2$. I'm not sure how this upper bound helps me.
The pairs (0,0), (1,1) ..., (n,n) can all be found when $A^2 = A.$ My intuition tells me that the answer should be $\{(a,b) : a,b \leq n$ and $a,b \geq 0\}$ but I have no clue how to prove that. Any ideas?
 A: Hint: Do the same problem but with nullity instead of rank. That's easier and more intuitive to think and reason about. Then use the rank-nullity theorem to translate.
A: Sylvester gives $\operatorname{rk} A^2 \ge 2 \operatorname{rk} A - n$ and you know that $\operatorname{rk} A^2 \le \operatorname{rk} A$.
So, you can guess that
$\max(0, 2 \operatorname{rk} A - n) \le \operatorname{rk} A^2 \le \operatorname{rk} A $, or
that $P= \{ (r,q) | \max(0,2r-n) \le q \le r \}$ is the set of pairs.
To finish we need to exhibit matrices with any value $(r,q) \in P$.
Let $\Lambda$ be a diagonal matrix with $r$ ones in the $(1,1),...,(r,r)$ positions and let $S $ be a 'right rotation', that is $S e_k = e_{k+1}, S e_n = e_1$. Then let $A = \Lambda S^{r-q}$ and note that $\operatorname{rk} = r$.
Note that $\Lambda e_k = \begin{cases} e_k, & k \le r \\
0, & \text{otherwise}\end{cases}$,
$\ \ S^{r-q}\Lambda e_k = \begin{cases} e_{k+r-q}, & k \le r \\
0, & \text{otherwise}\end{cases}$ and so
$\Lambda S^{r-q}\Lambda e_k = \begin{cases} e_{k+r-q}, & k \le q \\
0, & \text{otherwise}\end{cases}$.
Noting that $A^2 = S^{r-q} \Lambda S^{r-q}\Lambda $ it follows that $\operatorname{rk} A^2 = q$ and so $(r,q) \in P$.
