I'm working through Gilbert Strang's Introduction to Linear Algebra textbook (5th edition). In the problem set from section 3.3, exercise 25b asks to:
Write down all known relations between r and m and n if $Ax = \mathbf{b}$ has infinitely many solutions for every b.
My initial thought was that this matrix must have more columns n than rows m, thus leading to rank $r < n$. Additionally, this leads be to believe that this matrix may or may not have rows that are all zeroes, which might add some constraints to what the components of b could be, but would still lead to an infinite amount of solutions, as it still has free variables. Thus, my second answer was that $r \leq m$.
However, the answer from the solutions state:
The system has full row rank, and less than full column rank: $m = r < n$.
Why is this the solution?
Best Answer
We need $m=r$ since every $b$ needs to lie in the image of $A$, so the rank of the matrix (= dimension of the image) must equal the dimension of the codomain ($m$).
The condition about infinitely many solutions is equivalent to the kernel of $A$ being nontrivial; we know $n=r+\dim\ker A$ so I need $n>r$ with strict inequality.
If you like, the "less than full column rank" gives you the free variables idea, that any solution allows for infinitely many other solutions. The full row rank is what you need to guarantee the column rank $r=m$ which guarantees that every $b$ has at least one solution. E.g. inspect the RREF of the matrix. $A$ can not have rows which are all zeroes (in its RREF) as then $b=(0,0,\cdots,1)$ (relative to a basis compatible with the RREF) would not have any solutions at all.