Archive for March, 2010

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

March 19, 2010 5 comments

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.

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

Categories: Justincase Tags: , ,