# Prove: A matrix $A \in \mathbb{C}^{m \times n}$ with $m \geq n$ has full rank if and only if it maps no two distinct vectors to the same vector.

Thm. A matrix $A \in \mathbb{C}^{m \times n}$ with $m \geq n$ has full rank if and only if it maps no two distinct vectors to the same vector.

I'm going to write out the proof (given by my text) line by line because there are certain statements I'm not sure about. I'm a little rusty on linear algebra. For each statement of the proof, I'll give a statement from the proof and my analysis immediately below. The converse I will attempt to prove in my own words. Please give constructive feedback on correctness of my interpretation(s).

proof ($\implies$)

1. If A is of full rank, its columns are linearly independent, ...

Agreed. Since $m \geq n$ and full rank is defined my the maximum possible dimension spanned by the row or column spaces of $A$, then it must be that the rank of $A$ is $n$ which implies that the $n$ columns of A span $\mathbb{C}^n$. Which is only possible if the $n$ columns are linearly independent.

1. ... so they form a basis for range$(A)$.

I think I agree because, since the columns are L.I., they form a basis for $\mathbb{C}^n$, which is the column space of $A$ which is the range of $A$.

1. This means every vector $b \in \text{range}(A)$ has a unique linear expansion in terms of the columns of $A$, and therefore has a unique $x$ s.t $b = Ax$.

I have a strong intuition that the expansion is unique, since none of the columns of $A$ can be scaled to each other. But how is this statement proved? Do I consider $x,y$ such that $Ax = b$ and $Ay = b$ and then ($a_i$ are columns of $a$)

$$y_1a_1 + \cdots + y_na_n = x_1a_1 + \cdots + x_na_n$$ $$(y_1 - x_1)a_1 + \cdots + (y_n - x_n)a_n = 0$$

And since the columns are L.I. the only possible solution set is

$$\{y_1 - x_1 = 0, \dots , y_n - x_n = 0\} \implies x = y$$

Converse (proof by contraposition).

If $A$ is not of full rank then the columns of $A$ must be be linearly dependent. Therefore there is a nontrivial solution $x$ to the equation

$$Ax = x_1a_1 + \cdots + x_na_n = 0$$

This means that for any other vector $c \in \mathbb{C}^n$ we have

$$Ac = Ax + Ac = A(x+c)$$

so that $x+c$ and $c$ are mapped to the same vector $Ac$. That is, we have shown that if $A$ is not of full rank, then the mapping is not unique. So by contraposition, a unique mapping implies A is of full rank.

Sorry, that wasn't pretty.

## 1 Answer

Hint: Use Rank-Nullity Theorem