# Explain why a $n\times n$ matrix for which the trivial solution is the only solution to the homogeneous equation, has $n$ pivot columns.

I came across this simple exercise.

Suppose $A$ is $n\times n$ and the equation $A\textbf{x}=\textbf{0}$ has only the trivial solution. Explain why $A$ has $n$ pivot columns and $A$ is rowequivalent to $I_n$.

I understand that, because $A\textbf{x}=\textbf{0}$ implies $\textbf{x}=\textbf{0}$, $A$ must be invertible because $\bf{x} \mapsto A\bf{x}$ is one-to-one and if $A$ is invertible, it is obviously rowequivalent to $I_n$, but is there a more rigorous way to explain this?

-
If this question is by itself on an assignment or exam, you would perhaps want to spend a bit more space explaining each step, but if it's an (a) out of (a)-(d) or something, this amount of proof will do just fine in my opinion. There are some minor notational quirks, however. It's supposed to be $A\textbf{x}=\textbf{0}$, not $A\textbf{x}=\textbf{b}$, and $A\bf{x}\mapsto\bf{x}$ means $\bf{x}$ is an eigenvector. It is better to describe $A:\Bbb R^n\to\Bbb R^n$ as one-to-one. –  Arthur Oct 12 '12 at 9:42
I made an edit to change the b, Thanks for noticing. Anyway, It's just a small exercise, but I'm not sure if the step A must be invertible because the mapping is one-to-one is accurate as it is. –  Edward Stumperd Oct 12 '12 at 9:56
I would not call the matrix $A$ one-to-one, but rather the transformation $x \mapsto Ax$ one-to-one. –  Christopher A. Wong Oct 12 '12 at 10:00
@EdwardStumperd Well, see what happens if the mapping is one-to-one (and onto). Then you can for each vector find a single one that is being mapped to it, and thus creating a map "going the other way". This map would be described by some matrix $B$, since it's linear. By observing that $BA\bf x = \bf x$ for any vector, we have that $BA = I_n$ and therefore, $A$ must be invertible, with inverse $B$. It is important that the linear map given by $A$ is both one-to-one and onto, but these two are the same when $A$ is a square matrix. –  Arthur Oct 12 '12 at 10:05
@Edward Stumperd, since there is only trivial solution all row (column) vectors of $A$ are independent. So there are $n$ independent rows (columns). You get the rest from here. –  Mykolas Oct 12 '12 at 20:13

Consider $\mathcal{M}_n(\mathcal{F})$, the set of all $n \times n$ matrices, over a field $\mathcal{F}$. We define an equivalence relation $\cong$ on $\mathcal{M}_n(\mathcal{F})$ as follows: for $A,B \in \mathcal{M}_n(\mathcal{F})$, $A \cong B$ if there exists an invertible $P \in \mathcal{M}_n(\mathcal{F})$ such that $A=PB$. Then $I_n$ represents all $n \times n$ matrices of full rank, with respect to this row equivalence relation. Now, since $Ax=0 \Leftrightarrow x=0$, $A$ has full rank, and so it is inside the equivalence class of $I_n$, i.e. $A \cong I_n$, i.e. there exists invertible $P$ such that $A = P I_n$. This latter relation simply says that $A$ is invertible.