Home > Justincase > The solvability condition of A x = b when A is not a square matrix

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

Categories: Justincase Tags: , ,
1. March 19, 2010 at 11:10 am

We can view the equation as $x^T A^T=b^T$. In coding theory we say that $b^T$ is a codeword and $A^T$ is a generator matrix of a code $\mathcal{C}$. Then the left null space of $A$ is the parity check matrix of the code $\mathcal{C}$.

• March 29, 2010 at 1:28 pm

Hi pak Bara, nice information. thank you..

2. March 23, 2010 at 4:06 am

A very interesting post Ivanky! How are you at Lippo Karawaci? I hope you survive there well

• March 29, 2010 at 1:26 pm

Hi AJ, I am fine here thank you.. 🙂

3. August 4, 2013 at 8:53 pm

Hi! Quick question that’s totally off topic. Do you know how to make your site mobile friendly? My weblog looks weird when browsing from my apple iphone. I’m trying to find a theme or plugin that might be able to correct this problem. If you have any recommendations, please share. With thanks!|