Solving Linear Equations
2.3 Elimination using matrices
In linear algebra systems of linear equations are viewed as matrix-vector operations.
Identity Matrix
An identity matrix $I$ is $n \times n$ square matrix where the elements of the main diagonal are $1$ and rest are $0$.
Example:
\[I = \begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}\]It is a matrix that when multiplied with any other matrix gives the same matrix.
\[AI = IA = A\]Elimination matrix
As discussed in the previous chapter, we perform eliminations and row exchanges on $A$ to obtain $U$ which is an upper triangular matrix.
Each elimination step can be viewed as a matrix.
$E_{21}$ is a matrix that converts $2^{nd}$ row and $1^{st}$ column to 0.
\[E_{21}.A = U_{21}\] \[\begin{bmatrix}1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}.\begin{bmatrix}1 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{bmatrix}\] \[=\begin{bmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}\]All these steps can be combined to form a single elimination matrix.
\[E_{32}.E_{31}.E_{21} = E\] \[E.A = U\]Where $U$ is the upper triangular matrix.
\[A = E^{-1}U\] \[A = LU\]Where $L$ is the inverse of $E$. This allows us to get $A$ back from $U$.
Permutation matrix
Each row exchange step can be viewed as a matrix.
A Permutation matrix $P_{ij}$ lets us exchange the row $i$ with row $j$.
\[P_{31}= \begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix}\] \[A = \begin{bmatrix}0&2&3\\8&6&7\\5&9&4\end{bmatrix}\] \[P.A = \begin{bmatrix}5&9&4\\8&6&7\\0&2&3\end{bmatrix}\]Augmented Matrix
\[3x + 4y + 5z = 22\] \[2x + 5y + 7z = 23\] \[4x + 3y + 6z = 24\] \[\begin{bmatrix}3&4&5\\2&5&7\\4&3&6\end{bmatrix}.\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}22\\23\\24\end{bmatrix}\]All the eliminations steps and permutation steps that were applied on $A$ have to applied on the right side i.e. on $B$ as well.
\[AX = B\]So, to make it simpler we can add $B$ as a column to $A$ separated by ‘:’.
This is known as an augmented matrix.
Below, $E$ is the matrix formed by multiplying all the individual elimination matrices
\[E = \begin{bmatrix}1&0&0\\0&1&0\\0&1&1\end{bmatrix}.\begin{bmatrix}1&0&0\\0&1&0\\ \frac{-4}{3}&0&1\end{bmatrix}.\begin{bmatrix}1&0&0\\ \frac{-2}{3}&1&0\\0&0&1\end{bmatrix}\] \[E = \begin{bmatrix}1&0&0\\ \frac{-2}{3}&1&0\\-2&1&1\end{bmatrix}\] \[E.(A\;B)= \begin{bmatrix}1&0&0\\ \frac{-2}{3}&1&0\\-2&1&1\end{bmatrix}.\begin{bmatrix}3&4&5&:22\\2&5&7&:23\\4&3&6&:24\end{bmatrix}\] \[E.(A\;B)=\begin{bmatrix}3&4&5&:22\\0& \frac{7}{3}& \frac{11}{3}&: \frac{25}{3}\\0&0&3&:3\end{bmatrix}\]Now this can be solved with back substitution.
\[3x + 4y + 5z = 22\] \[\frac{7}{3}y + \frac{11}{3}z = 23\] \[3z = 3\]Rules for matrix multiplication
Associative law
\[A(BC) = (AB)C\]Commutative law
\[AB \neq BA\]2.4 Rules for Matrix Operations
Matrix $A$ with $n$ columns can multiply matrix $B$ with $n$ rows :
\[A_{mxn}.B_{nxp} = C_{mxp}\]If this condition is not satisfied then the matrices cannot be multiplied.
First way
Take the dot product of each row of A with each column of B:
Here, \(C_{ij} = A_{i^{th} row}.B_{i^{th} col}\).
For example :
\[\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}.\begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{bmatrix}\] \[=\begin{bmatrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22} \\ a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22} \end{bmatrix}\]Second way
Matrix $A$ times every column of $B$:
\[\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}.\begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{bmatrix}\] \[=\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}.\begin{bmatrix} b_{11} \\ b_{21} \end{bmatrix} and \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}.\begin{bmatrix} b_{12} \\ b_{22} \end{bmatrix}\]The result of the first matrix-vector multiplication gives the elements of the first column.
The result of the second matrix-vector multiplication gives the elements of the second column.
\[=\begin{bmatrix} a_{11}b_{11}+a_{12}b_{21} && a_{11}b_{12}+a_{12}b_{22} \\ a_{21}b_{11}+a_{22}b_{21} && a_{21}b_{12}+a_{22}b_{22} \end{bmatrix}\]In $AB = C$, each column of $C$ is the linear combination of the columns of $A$. Where the constants are taken from the columns of $B$.
Third way
Each row of $A$ multiplies the whole matrix $B$. The result is a row of $C$.
\[C = \begin{bmatrix}A_{row1}.B &.&.\\ A_{row2}.B&.&.\\A_{row3}.B&.&.\end{bmatrix}\]This approach takes us back to the first or second approach.
Because we still have to calculate
\[A_{i^{th}row}.B\]Fourth way
Multiply columns $1$ to $n$ of $A$ times rows $1$ to $n$ of $B$:
\[\begin{bmatrix} a_{11} \\ a_{21} \end{bmatrix}.\begin{bmatrix} b_{11} & b_{12} \end{bmatrix} + \begin{bmatrix} a_{12} \\ a_{22} \end{bmatrix}.\begin{bmatrix} b_{21} & b_{22} \end{bmatrix}\] \[=\begin{bmatrix} a_{11}b_{11} && a_{11}b_{12} \\ a_{21}b_{11} && a_{21}b_{12} \end{bmatrix}+\begin{bmatrix} a_{12}b_{21} && a_{12}b_{22} \\ a_{22}b_{21} && a_{22}b_{22} \end{bmatrix}\] \[=\begin{bmatrix} a_{11}b_{11}+a_{12}b_{21} && a_{11}b_{12}+a_{12}b_{22} \\ a_{21}b_{11}+a_{22}b_{21} && a_{21}b_{12}+a_{22}b_{22} \end{bmatrix}\]2.5 Inverse Matrix
- An inverse of $A$ i.e. $A^{-1}$ when multiplied with $A$ gives the identity matrix.
- When taken from left to right $A$ becomes $A^{-1}$.
-
Not all matrices have inverses.
-
Only square matrices with linearly independent rows and columns are invertible.
-
If the inverse of a matrix does not exist it is called a non-invertible matrix.
Testing Inverse
-
If matrix is
diagonally dominant
, it has inverse. -
$A^{-1}$ exists iff elimination produces $n$
pivot points
. That is no diagonal element should be zero. -
Matrix $A$ cannot have two different inverses which means while solving $AX=B$ for $X$
-
$X$ is a unique solution.
-
If $AX = 0$, and $X \neq 0$ then $A^{-1}$ does not exist.
-
$A^{-1}$ exists if determinant of $A \neq 0$.
Diagonally dominant
A square matrix is said to be diagonally dominant if for every row the diagonal element is greater than the sum of the other elements.
\[A =\begin{bmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\a_{31} & a_{32} & a_{33}\end{bmatrix}\]If $A$ is diagonally dominant $a_{11} > a_{12} + a_{13}$ , $a_{22} > a_{21} + a_{23}$ and so on.
The inverse of a product
If $A$ and $B$ are invertible. Then $AB$ is also invertible.
\[B^{-1} A^{-1} = (AB)^{-1}\] \[C^{-1} B^{-1} A^{-1} = (ABC)^{-1}\]Calculating $A^{-1}$ using Gauss-Jordan
Consider a matrix $K$.
\[K= \begin{bmatrix}2 & -1 & 0 \\-1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}\]Let there be a sequence of elimination steps that can convert $K$ to $I$.
These steps can be written as elimination matrices.
\[E_{21}.E_{31}....K = I\]The elimination matrices can be represented as a single matrix.
\[EK = I\]It is obvious that $E$ is nothing but $K^{-1}$.
If we multiply the same matrix $E$ with $I$
\[EI = E = K^{-1}\]Thus, it can be said that the sequence of steps that converts $K$ to $I$ also converts $I$ to $K^{-1}$
Gauss-Jordan method uses this concept on an augmented matrix to compute the inverse of a matrix.
\[K\;I= \begin{bmatrix}2 & -1 & 0 & :1 & 0 & 0\\-1 & 2 & -1 & :0 & 1 & 0 \\ 0 & -1 & 2 & :0 & 0 & 1 \end{bmatrix}\]Perform Row Elimination
Use the pivots to convert to upper triangular form.
\[= \begin{bmatrix}2 & -1 & 0 & :1 & 0 & 0\\0 & \frac{3}{2} & -1 & :\frac{1}{2} & 1 & 0\\0 & 0 & \frac{4}{3} & :\frac{1}{3} & \frac{2}{3} & 1\end{bmatrix}\]Zero above pivots
Use the pivots again to convert each element above the pivot to zero.
\[= \begin{bmatrix}2 & 0 & 0 & :\frac{3}{2} & 1 & \frac{1}{2}\\0 & \frac{3}{2} & 0 & :\frac{3}{4} & \frac{3}{2} & \frac{3}{4} \\ 0 & 0 & \frac{4}{3} & :\frac{1}{3} & \frac{2}{3} & 1\end{bmatrix}\]Divide row by diagonal elements
Divide each row by the diagonal element of that row to obtain identity matrix on the left.
\[= \begin{bmatrix}1 & 0 & 0 & :\frac{3}{4} & \frac{1}{2} & \frac{1}{4}\\0 & 1 & 0 & :\frac{1}{2} & 1 & \frac{1}{2} \\ 0 & 0 & 1 & :\frac{1}{4} & \frac{1}{2} & \frac{3}{4}\end{bmatrix}\] \[=I\;K^{-1}\]- If $K$ is symmetric then $K^{-1}$ is also symmetric.
2.6 Elimination = Factorization : LU
- $EA = U$, $U$ is an upper triangular matrix.
- $E^{-1} = L$
- Then the original matrix $A$ can be recovered by $A = LU$
- Elimination on $AX = B$ gives $UX = C$.
Transposes and permutations
Transpose
Transpose of a matrix means to exchange its rows and columns.
\[A = \begin{bmatrix}1&2\\3&4\\5&6\end{bmatrix}\] \[A^{T} = \begin{bmatrix}1&3&5\\2&4&6\end{bmatrix}\]Although it looks quite simple, transpose has a lot of uses which we will discuss in chapters to come.
A sneak-peak :
Consider a two vectors as single column matrices,
\[A = \begin{bmatrix}a\\b\end{bmatrix}, B = \begin{bmatrix}c\\d\end{bmatrix}\]Then the dot product $A.B$ is just the matrix multiplication of $A^{T}$ and $B$.
\[A^{T}B = \begin{bmatrix}a & b\end{bmatrix}\begin{bmatrix}c\\d\end{bmatrix}\] \[A^{T}B = ac+bd\]Some rules for transpose
\[(A+B)^{T} = A^{T} + B^{T}\] \[(A.B)^{T} = B^{T}.A^{T}\] \[(A^{-1})^{T} = (A^{T})^{-1}\]- If $A$ is invertible $A^{T}$ is also invertible.
Symmetric matrices
- $S$ is a symmetric matrix if $S = S^{T}$
Summary
- Each elimination step can be viewed as a matrix.
- All the steps can be combined to form a single elimination matrix.
- All the eliminations steps that were applied on $A$ have to applied on the right side i.e. on $B$ as well.
- So, to make it simpler we can add $B$ as a column to $A$ separated by ‘:’.
-
This is known as an augmented matrix.
- Associative law
- Commutative law
- Matrix $A$ with $n$ columns can multiply matrix $B$ with $n$ rows :
- An inverse of $A$ i.e. $A^{-1}$ when multiplied with $A$ gives the identity matrix.
- When taken from left to right $A$ becomes $A^{-1}$.
-
Only square matrices with linearly independent rows and columns are invertible.
-
$A^{-1}$ exists if determinant of $A \neq 0$.
-
Inverse
-
The sequence of steps that converts $K$ to $I$ also converts $I$ to $K^{-1}$
-
$EA = U$
-
$E^{-1} = L$
-
The original matrix $A$ can be recovered by $A = LU$
-
Transpose of a matrix means to exchange its rows and columns
- $S$ is a symmetric matrix if $S = S^{T}$
References
- Introduction to Linear Algebra, W. G. Strang
- Essence of linear algebra : https://www.3blue1brown.com/