### Archive

Archive for March, 2010

## The solvability condition of A x = b when A is not a square matrix

In an elementary linear algebra course, we learned the solvability condition of the linear system

$A \mathbf{x} =\mathbf{ b}$

where $A$ is an $n \times n$ matrix and $\mathbf{x}, \mathbf{b}$ are $n \times 1$ vectors.

To mention a few, the followings are the solvability conditions (equivalent conditions) such that the linear system above has a solution:

1. determinant of $A$ is not zero
2. rank of $A$ is full
3. all eigenvalues of $A$ are non zero
4. the vector columns (also rows) are independent
5. $A$ has an inverse
6. et cetera

However, I would like to discuss the case when either (#) $A$ is not a square matrix or
(##) the rank of $A$ is not full (< $latex n$).

There is actually a condition such that the linear system $A \mathbf{x} = \mathbf{b}$ has a solution whenever we have either (#) or (##). The solvability condition is

$\mathbf {b} \in Col(A)$.

The thing is this condition is not applicable to most problems I have ever had. For instances, I bumped into the following problem.

Let $A, \mathbf{x}, \mathbf{b}$ be the following

$A=\left(\begin{array}{cc}a_{11} & a_{21} \\a_{12} & a_{22} \\b_{1} &b_{2} \\\end{array}\right)$$\mathbf{x} = (l_1, l_2)^T$ and $\mathbf{b}=(-a_{11},-a_{22},0)^T$. I want to seek a condition such that the linear system $A \mathbf{x}=\mathbf{b}$ is solvable for $l_1,l_2$. I want to find a condition for $a_{ij}$ and $b_i$ such that there is a solution of $l_1, l_2$.

The statement $\mathbf{b} \in Col(A)$ did not help me at that time and I look for another implication for this statement that is applicable enough to my problem.

Fundamental Theorem of Orthogonality (see [1])
Let $A$ be any $m \times n$ matrices.  The row space of $A$ is orthogonal to the null space of $A$.

Proof: Suppose $\mathbf{x}$ is a vector in the nullspace. Then $A \mathbf{x} = 0$. This equation can be considered as rows of $A$ multiplying $\mathbf{x}$:

$A\mathbf{x}$ = $\left[\begin{array}{ccc}\cdots & row_1 & \cdots \\\cdots & row_2 & \cdots \\ \phantom{a} & \phantom{a} & \phantom{a} \\ \cdots & row_m & \cdots \\ \end{array}\right]\left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \\ \end{array} \right]$ = $\left[\begin{array}{c} 0 \\ 0 \\ \vdots \\ 0 \\ \end{array} \right]$.

We can clearly see that a dot product of row 1 and $\mathbf{x}$ is zero, a dot product of row 2 and $\mathbf{x}$ is zero, and so on. This means that the dot product of every row of $A$ and $\mathbf{x}$ is zero, which means every row of $A$ is orthogonal to $\mathbf{x}$, which completes the proof.

Corrolary 1
The column space of $A$ is orthogonal to the left null space of $A$.

Proof: The proof is easy, we just need to consider the transpose of the matrix $A$.

Going back to our original problem, when the vector $\mathbf{b}$ is in the column space of $A$, the vector will be orthogonal to any vector in the left null space of $A$.

Thus, we have the following solvability condition:

Solvability condition of $A \mathbf{x} = \mathbf{b}$ for any matrices $A$
The linear system $A\mathbf{x}=\mathbf{b}$ has a solution if the dot product of $\mathbf{b}$ and $\mathbf{y}_i$ is zero, where $\mathbf{y}_i$ is the base vector of the left null space of $A$.

Remark, the above solvability condition is closely related to the linear version of Fredholm solvability condition.

Reference
[1] Strang, G., “Linear Algebra and Its Applications,” Thomson Brooks/Cole