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

Advertisements
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}.

    • ivanky
      March 29, 2010 at 1:28 pm

      Hi pak Bara, nice information. thank you..

  2. Albert
    March 23, 2010 at 4:06 am

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

    • ivanky
      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!|

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: