Solving $A\vec{x}=\vec{b}$

Say we have a matrix

\(A\)

we need to find solution space for

A\vec{x}=\vec{b}

for any given

\vec{b}

.
Let's consider same example we took in Null space discussion.

A=\begin{bmatrix} 1 & 2 & 2 & 2\\ 2 & 4 & 6 & 8\\ 3 & 6 & 8 & 10\\ \end{bmatrix}

A\vec{x} = \begin{bmatrix} 1 & 2 & 2 & 2\\ 2 & 4 & 6 & 8\\ 3 & 6 & 8 & 10\\ \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3\\x_4\\ \end{bmatrix} = \begin{bmatrix} b_1\\b_2\\b_3\\ \end{bmatrix}

It give us a set of equations:

\begin{matrix} x_1 & + & 2x_2 & + & 2x_3 & + & 2x_4 & = & b_1 \\ 2x_1 & + & 4x_2 & + & 6x_3 & + & 8x_4 & = & b_2 \\ 3x_1 & + & 6x_2 & + & 8x_3 & + & 10x_4 & = & b_3 \\ \end{matrix}

A\vec{x}

is just a linear combinations of column vector of matrix

\(A\)

, so the resultant of this linear combination must lie in the column space of

\(A\)

. So

$A\vec{x}=\vec{b}$ is solvable if $\vec{b}$ lies in the column space of $$A$$

How can we find all the $\vec{x}$ that solves $A\vec{x}=\vec{b}$ ?

Let's find a solution for

A\vec{x}=\vec{b}

Now we have to find a particular

\vec{x}

that solves

A\vec{x}=\vec{b}

, say this particular solution be

\vec{x}_p

Our matrix is

A=\begin{bmatrix} 1 & 2 & 2 & 2\\ 2 & 4 & 6 & 8\\ 3 & 6 & 8 & 10\\ \end{bmatrix}

First we convert our matrix in echelon form using Elimination technique, and unlike in null space here we also have

\(b_i\)

's so we use Augmented matrix.

So our Augmented matrix is:

\left[ \begin{array}{cccc|c} 1 & 2 & 2 & 2 & b_1\\ 2 & 4 & 6 & 8 & b_2\\ 3 & 6 & 8 & 10 & b_3\\ \end{array} \right]

Now let's do elimination.
Step 1: of elimination method, here we make all element

\(0\)

\(c_1\)

below the

1^{st}

element.

r_2\leftarrow r_2 - 2r_1

\left[ \begin{array}{cccc|c} 1 & 2 & 2 & 2 & b_1\\ 0 & 0 & 2 & 4 & b_2-2b_1\\ 3 & 6 & 8 & 10 & b_3\\ \end{array} \right]

r_3\leftarrow r_3 - 3r_1

\left[ \begin{array}{cccc|c} \fbox{1} & 2 & 2 & 2 & b_1\\ 0 & 0 & 2 & 4 & b_2-2b_1\\ 0 & 0 & 2 & 4 & b_3-3b_1\\ \end{array} \right]

Step 2: of elimination method, here we make all element

\(0\)

\(c_2\)

below the

2^{nd}

element.
But

2^{nd}

element itself is

\(0\)

, and all element below it also

\(0\)

, so we move forward.

Step 3: of elimination method, here we make all element

\(0\)

\(c_3\)

below the

2^{nd}

element.

\left[ \begin{array}{cccc|c} \fbox{1} & 2 & 2 & 2 & b_1\\ 0 & 0 & 2 & 4 & b_2-2b_1\\ 0 & 0 & 2 & 4 & b_3-3b_1\\ \end{array} \right]

r_3\leftarrow r_3-r_2

\left[ \begin{array}{cccc|c} \fbox{1} & 2 & 2 & 2 & b_1 \\ 0 & 0 & \fbox{2} & 4 & b_2 -2b_1 \\ 0 & 0 & 0 & 0 & b_3 -b_2 - b_1\\ \end{array} \right]

(Notice the last row it indicates that

\(b_3 -b_2 - b_1=0\)

.)
Here

\(c_2,c_4\)

are free columns, and

\(c_1,c_3\)

are pivot columns, we discussed about them in Null space section.
So

\(x_2,x_4\)

are free variable we are free to assign any value to them. So say

\(x_2=x_4=0\)

Now say we want to find solution space for

A\vec{x}_p= \begin{bmatrix} 1\\5\\6\\ \end{bmatrix}

(

\(b_3 -b_2 - b_1=6-5-1=0\)

so it's a valid question to ask )
So our system of equation becomes:

\begin{matrix} x_1 & + & 0 & + & 2x_3 & + & 0 & = & 1 \\ 0 & + & 0 & + & 2x_3 & + & 0 & = & 5-2*1 \\ 0 & + & 0 & + & 0 & + & 0 & = & 6-5-1 \\ \end{matrix}

by solving them:

\(x_3=3/2, x_1=-2\)

\vec{x}_p=\begin{bmatrix} -2\\0\\3/2\\0\\ \end{bmatrix}

Remember our approach when we are finding Null Space:
We were finding solution for $A\vec{x}=0$ and what we did is, we took our free variables, and iteratively we set one free variable to $$1$$ and all other free variables to $$0$$ .
By this we create multiple special solutions and each special solution consider a particular free column vector.
Then we took linear combination of all of those special solutions.

Now here what we are doing is, we aren't considering any of the free column vector, because our Null space had already considered them for us.
Now say

\vec{x}_n

represent the Null Space of matrix

\(A\)

, so

A\vec{x}=0;\quad x\in x_n

\vec{x}_n

represents a vector space(it's not a single vector), it's a linear combination of bunch of vectors.
So complete solution for

A\vec{x}=\vec{b}

is:

$\vec{x} = \vec{x}_p+\vec{x}_n$

So any

\vec{x}\in\vec{x}_p+\vec{x}_n

solves

A\vec{x}=\vec{b}

But remember that $\vec{x}_p$ is a vector, and $\vec{x}_n$ is a vector space it's some $$d$$ -dimensional subspace.
How can we add a vector $\vec{x}_p$ and a subspace $\vec{x}_n$ ?
Think about a surface in $$3$$ -dimensions, let's say that surface is a plane then when we add a vector to a plane, we are just shifting that plane in the direction of vector.
So $\vec{x}_p$ is just shifting the Null Space in it's direction.
And when $\vec{x}_p$ shifts the Null space then the shifted space is no longer in contact with origin, so the resultant space $\vec{x}_p+\vec{x}_n$ is not a subspace.

As we derived Null space of

\(A\)

in Null space section.

\vec{x}_n=\alpha \begin{bmatrix} -2\\1\\0\\0\\ \end{bmatrix} + \beta \begin{bmatrix} 2\\0\\-2\\1\\ \end{bmatrix};\quad

\alpha,\beta\in\mathbb{R}

So complete solution for our example is:

\vec{x} = \begin{bmatrix} -2\\0\\3/2\\0\\ \end{bmatrix} + \alpha \begin{bmatrix} -2\\1\\0\\0\\ \end{bmatrix} + \beta \begin{bmatrix} 2\\0\\-2\\1\\ \end{bmatrix} ;\quad

\alpha,\beta\in\mathbb{R}

So the solution space of $A\vec{x}_p= \begin{bmatrix} 1\\5\\6\\ \end{bmatrix}$ is a plane in $\mathbb{R}^4$ .

Solving \(A\vec{x}=\vec{b}\)

How can we find all the \(\vec{x}\) that solves \(A\vec{x}=\vec{b}\)?

Solving $A\vec{x}=\vec{b}$

How can we find all the $\vec{x}$ that solves $A\vec{x}=\vec{b}$ ?