Matrix equation $AX=B$

Question

I'm interested in the equation $$AX=B$$ where $A, X,$ and $B$ are rectangular matrices with suitable dimensions, for example $m\times n$, $n\times p$, $m\times p$. Exploring with Maple I see that $4\times 2$, $2\times 3$, $4\times 3$ have generally the unique solution $ (A^TA)^{-1}A^TB$; with $3\times 5$, $5\times 2$, $3\times 2$ instead the equation has no solution because $(A^TA)$ is not invertible.

Do you know any condition in order to claim that $(A^TA)$ is invertible or the equation $AX=B$ has just one solution?

Answer 1

If $m < n$ then $A^TA$ will always be uninvertible. The reason is since $A$ was a map from $\Bbb{R}^n$ to $\Bbb{R}^m$ (in this case, a higher dimensional space to a lower dimensional one) we are guaranteed that there will be a nontrivial null space (in fact, $\dim \ker A \geq n-m)$. Even though $A^T$ is a map back to $\Bbb{R}^n$ from $\Bbb{R}^m$, we will not retrieve those lost dimensions due to linearity since if $v\in\ker A$

$$A^TAv = A^T 0 = 0$$

Another way of phrasing this is that if $m<n$, then $A^TA$ is guaranteed to have an eigenvalue of $0$.

For the reverse case when $m > n$, $A$ has a chance to, but not guaranteed to, be invertible. What we require in this case is for $A$ to be full rank, or $\dim \text{range }A = n $. If you are familiar with singular values, this is exactly the condition needed to guarantee that all singular values are nonzero.

Answer 2

You can think of $AX=B$ as a collection of $p$ equations $Ax_1 = b_1$, $Ax_2 = b_2$, ..., $Ax_p = b_p$ where $x_k$ and $b_k$ are the $k$-th columns of $X$ and $B$.

Existence: For each individual equation it's basic linear algebra: a solution exists if and only if $b_k ∈ \text{Im}(A)$. So, for the collection of the $p$ equations a solution exists if and only if $\{b_1, …, b_p\}⊆\text{Im}(A)$, or, equivalently, if and only if

$$ \text{Im}(B) ⊆ \text{Im}(A)$$

Uniqueness: Even if only a single one of the $p$ equations has not a unique solution, the set of equation won't have a unique solution as the equations are de-coupled ($x_k$ only appears in the $k$-th equation). For the individual equations a solution is unique if and only if

$$ \ker(A) = \{0\}$$