[Math] Prove that if the columns of the $m\times n$ matrix $A$ are linearly independent, then $Ax=b$ has at most one solution.

linear algebramatricesproof-verificationvector-spaces

Prove that if the columns of the $m\times n$ matrix $A$ are linearly independent, then $Ax=b$ has at most one solution.

I was thinking that if the $n$ columns are linearly independent, then the dimension of the column space is $n$, which implies the dimension of the row space is $n$ also. Hence $A$ is $n\times n$, but wouldn't this imply there's exactly one solution of $Ax=b$ rather than at most one?

Is this logic correct, or am I missing something?

Best Answer

Let $A = \begin{bmatrix}\mathbf{a}_1 & \mathbf{a}_2 & \cdots & \mathbf{a}_n\end{bmatrix}$ and $\mathbf{x} = \begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix}$ and $\mathbf{b} = \begin{bmatrix}b_1\\b_2\\\vdots\\b_m\end{bmatrix}$.

Now, $A\mathbf{x} = x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + \cdots + x_n\mathbf{a}_n$.

Let $\mathbf{u}$ and $\mathbf{v}$ be two solutions of $A \mathbf{x} = \mathbf{b}$. Then, we have:

$$\begin{cases} u_1 \mathbf{a}_1 + u_2 \mathbf{a}_2 + \cdots + u_n\mathbf{a}_n &=& \mathbf{b} & (1)\\ v_1 \mathbf{a}_1 + v_2 \mathbf{a}_2 + \cdots + v_n\mathbf{a}_n &=& \mathbf{b} & (2) \end{cases}$$

Subtract $(2)$ from $(1)$ to get:

$$(u_1-v_1) \mathbf{a}_1 + (u_2-v_2) \mathbf{a}_2 + \cdots + (u_n-v_n) \mathbf{a}_n = 0$$

Using the fact that $\mathbf{a}_1$ through $\mathbf{a}_n$ are linearly independent, we get $u_1-v_1 = u_2-v_2 = \cdots = u_n-v_n = 0$, i.e. $u_i=v_i$, i.e. $\mathbf{u} = \mathbf{v}$.

Related Solutions

[Math] How to find linearly independent columns in a matrix

Given $A\in\mathbb{R}^{m\times n}$, $m\geq n$, compute the (economy) QR factorisation. This gives $$ A = QR, \quad R\in\mathbb{R}^{n\times n}. $$ Now if $\mathrm{rank}(A)<n$, the upper triangular matrix $R$ has a staircase profile with some of the "steps" of the staircase over more than one column. Select column indices $j_1,\ldots,j_k$ such that if you remove these columns from $R$, you obtain a nonsingular upper triangular matrix (you can consider it as making each step of the staircase of length 1). The columns $j_1,\ldots,j_k$ can be expressed as linear combination of the remaining columns.

Example: The red columns indicate the columns which are linear combinations of the others.

$$ \begin{bmatrix} \times & \times & \color{red}\times & \times & \color{red}\times & \color{red}\times \\ 0 & \times & \color{red}\times & \times & \color{red}\times & \color{red}\times \\ 0 & 0 & \color{red}0 & \times & \color{red}\times & \color{red}\times \end{bmatrix} $$

Example: For the given matrix from the question, the QR factorisation is:

Q =

         0   -0.4472   -0.8944
         0   -0.8944    0.4472
   -1.0000         0         0

R =

   -1.0000    2.0000   -1.0000
         0    4.4721   -2.2361
         0         0         0

So one can pick the column 2 or 3 to make the matrix $R$ nonsingular and upper triangular (hence either the column 2 or 3 is a linear combination of the others).

Linear Algebra – Proof of Linearly Independent Columns in Invertible Matrix

I would say that the textbook's proof is better because it proves what needs to be proven without using facts about row-operations along the way. To see that this is the case, it may help to write out all of the definitions at work here, and all the facts that get used along the way.

Definitions:

$A$ is invertible if there exists a matrix $A^{-1}$ such that $AA^{-1} = A^{-1}A = I$
The vectors $v_1,\dots,v_n$ are linearly independent if the only solution to $x_1v_1 + \cdots + x_n v_n = 0$ (with $x_i \in \Bbb R$) is $x_1 = \cdots = x_n = 0$.

Textbook Proof:

Fact: With $v_1,\dots,v_n$ referring to the columns of $A$, the equation $x_1v_1 + \cdots + x_n v_n = 0$ can be rewritten as $Ax = 0$. (This is true by definition of matrix multiplication)

Now, suppose that $A$ is invertible. We want to show that the only solution to $Ax = 0$ is $x = 0$ (and by the above fact, we'll have proven the statement).

Multiplying both sides by $A^{-1}$ gives us $$ Ax = 0 \implies A^{-1}Ax = A^{-1}0 \implies x = 0 $$ So, we may indeed state that the only $x$ with $Ax = 0$ is the vector $x = 0$.

Your Proof:

Fact: With $v_1,\dots,v_n$ referring to the columns of $A$, the equation $x_1v_1 + \cdots + x_n v_n = 0$ can be rewritten as $Ax = 0$. (This is true by definition of matrix multiplication)

Fact: If $A$ is invertible, then $A$ is row-equivalent to the identity matrix.

Fact: If $R$ is the row-reduced version of $A$, then $R$ and $A$ have the same nullspace. That is, $Rx = 0$ and $Ax = 0$ have the same solutions

From the above facts, we conclude that if $A$ is invertible, then $A$ is row-equivalent to $I$. Since the columns of $I$ are linearly independent, the columns of $A$ must be linearly independent.