Problem: What multiple \(l_{32}\) of row 2 of \(A\) will elimination subtract from row 3 of \(A\)? Use the factored form \(A=\overset {L}{\overbrace {\begin {bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 1 & \fbox {4} & 1 \end {bmatrix} }}\overset {U}{\overbrace {\begin {bmatrix} 5 & 7 & 8\\ 0 & 2 & 3\\ 0 & 0 & 6 \end {bmatrix} }}\)what will be the pivots? will a row exchange be required?
Solution:
\(l_{32}=4\), hence elimination will subtract \(4\) times row \(2\) from row 3.
Looking at the \(U\) matrix, we see the pivots along the diagonal of the matrix: \(\begin {bmatrix} \fbox {$5$} & 7 & 8\\ 0 & \fbox {$2$} & 3\\ 0 & 0 & \fbox {$6$}\end {bmatrix} \)
To find out if a row exchange will be needed or not, first determine \(A\)
Carry the first elimination, we get
Hence, there would not be a need for a row exchange.
Problem: Factor \(A\) into \(LU\) and write down the upper triangular system \(Ux=c\) which appears after elimination for
Answer:
\(A=\begin {bmatrix} \fbox {$2$} & 3 & 3\\ 0 & 5 & 7\\ 6 & 9 & 8 \end {bmatrix} \overset {l_{21}=0}{\Rightarrow }\begin {bmatrix} \fbox {$2$} & 3 & 3\\ 0 & 5 & 7\\ 6 & 9 & 8 \end {bmatrix} \overset {l_{31}=3}{\Rightarrow }\begin {bmatrix} 2 & 3 & 3\\ 0 & \fbox {$5$} & 7\\ 0 & 0 & -1 \end {bmatrix} \overset {l_{32}=0}{\Rightarrow }\begin {bmatrix} 2 & 3 & 3\\ 0 & 5 & 7\\ 0 & 0 & \fbox {$-1$}\end {bmatrix} \)
Hence
and
Hence now we can write \(Ax=b\) as \(\left ( LU\right ) x=b\), or \(L\left ( Ux\right ) =b\), Where \(Ux=c\)
We can solve for \(c\) by solving \(Lc=b\), then we solve for \(x\) by solving \(Ux=c\)
Problem: Find \(E^{2}\) and \(E^{8}\) and \(E^{-1}\) if \(E=\begin {bmatrix} 1 & 0\\ 6 & 1 \end {bmatrix} \)
Answer:
\(E^{2}\left ( A\right ) \) means \(E\left ( E\left ( A\right ) \right ) \), which means we first subtract \(-6\) times first row from second row of \(A\), then apply \(E\) to this result again, subtracting \(-6\) times first row from the second row of the resulting matrix.
Hence the net result is subtracting \(-12\) times first row from the second row of the original matrix \(A.\)
Hence in general, we write
Therefore
Problem: (a) Under what conditions is the following product non singular?
(b) Solve the system \(Ax=b\) starting with \(Lc=b\)
Solution:
(a) Since \(U=\left [ D\right ] \left [ V\right ] =\begin {bmatrix} d_{1} & 0 & 0\\ 0 & d_{2} & 0\\ 0 & 0 & d_{3}\end {bmatrix}\begin {bmatrix} 1 & -1 & 0\\ 0 & 1 & -1\\ 0 & 0 & 1 \end {bmatrix} =\begin {bmatrix} d_{1} & -d_{1} & 0\\ 0 & d_{2} & -d2\\ 0 & 0 & d_{3}\end {bmatrix} \)
Hence the elements along the diagonal of \(U\) are the pivots. Then if any one of \(d_{1},d_{2},d_{3}\) is zero, then \(A\) will be non-singular
Hence for \(A\) to be non singular, then \(d_{1}\) and \(d_{2}\) and \(d_{3}\) must all be nonzero.
(b)
\(Lc=b\) where \(Ux=c\)
hence starting with \(Lc=b\) we write
Solve for \(c\) by back substitution process \(\Rightarrow \) \(c_{1}=0\), \(c_{2}=0\), \(c_{3}=1\)
Hence now we write \(\left [ U\right ] x=c\) or
Solve for \(x\) by back substitution process \(\Rightarrow \)
and from second row, \(d_{2}x_{2}-d_{2}x_{3}=0\Rightarrow d_{2}x_{2}-\frac {d_{2}}{d_{3}}=0\), hence
and from the first row, we have \(x_{1}d_{1}-x_{2}d_{1}=0\), hence \(x_{1}d_{1}=\frac {d_{1}}{d_{3}}\) \(\Rightarrow x_{1}=\frac {1}{d_{3}}\)
Problem: What three elimination matrices \(E_{21},E_{31},E_{32}\) put \(A\) into upper triangular form \(E_{32}E_{31}E_{21}A=U?\) Multiply by \(E_{32}^{-1},E_{31}^{-1},E_{21}^{-1}\) to factor \(A\) into \(LU\) where \(L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}\). Find \(L\) and \(U\)
Solution:
\(\overset {A}{\overbrace {\begin {bmatrix} 1 & 0 & 1\\ 2 & 2 & 2\\ 3 & 4 & 5 \end {bmatrix} }}\overset {l_{21}=2}{\Rightarrow }\begin {bmatrix} 1 & 0 & 1\\ 0 & 2 & 0\\ 3 & 4 & 5 \end {bmatrix} \overset {l_{31}=3}{\Rightarrow }\begin {bmatrix} 1 & 0 & 1\\ 0 & 2 & 0\\ 0 & 4 & 2 \end {bmatrix} \overset {l_{32}=2}{\Rightarrow }\overset {U}{\overbrace {\begin {bmatrix} \fbox {$1$} & 0 & 1\\ 0 & \fbox {$2$} & 0\\ 0 & 0 & \fbox {$2$}\end {bmatrix} }}\)
Hence \(E_{21}=\begin {bmatrix} 1 & 0 & 0\\ -l_{21} & 1 & 0\\ 0 & 0 & 1 \end {bmatrix} ,E_{31}=\begin {bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ -l_{31} & 0 & 1 \end {bmatrix} ,E_{32}=\begin {bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -l_{32} & 1 \end {bmatrix} \)
i.e. \(E_{21}=\begin {bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 0 & 0 & 1 \end {bmatrix} ,E_{31}=\begin {bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ -3 & 0 & 1 \end {bmatrix} ,E_{32}=\begin {bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -2 & 1 \end {bmatrix} \)
Hence \(L=\begin {bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 3 & 2 & 1 \end {bmatrix} ,U=\begin {bmatrix} 1 & 0 & 1\\ 0 & 2 & 0\\ 0 & 0 & 2 \end {bmatrix} \)
Problem: If \(P_{1}\) and \(P_{2}\) are permutation matrices, so is \(P_{1}P_{2}\). This still has the rows of \(I\) in some order. Give examples with \(P_{1}P_{2}\neq P_{2}P_{1}\), and examples of \(P_{3}P_{4}=P_{4}P_{3}\)
Solution:
A permutation matrix exchanges one row with another. It is used when the pivot is zero.
Assume \(P_{1}\) exchanges row \(i\) with row \(j.\) Assume \(P_{2}\) exchanges row \(k\) with row \(l.\) Hence \(P_{1}P_{2}\) exchanges row \(k\) with row \(l\) and next exchanges row \(i\) with row \(j\) of the resulting matrix.
For specific examples, Let \(P_{2}\) exchange second row with third row, and let \(P_{1}\) exchange second row with third row. Given \(A=\begin {bmatrix} R_{1}\\ R_{2}\\ R_{3}\end {bmatrix} \) hence \(P_{1}P_{2}\left ( A\right ) =P_{1}P_{2}\begin {bmatrix} R_{1}\\ R_{2}\\ R_{3}\end {bmatrix} =P_{1}\begin {bmatrix} R_{1}\\ R_{3}\\ R_{2}\end {bmatrix} =\begin {bmatrix} R_{3}\\ R_{1}\\ R_{2}\end {bmatrix} \)
While \(P_{2}P_{1}\left ( A\right ) =P_{2}P_{1}\begin {bmatrix} R_{1}\\ R_{2}\\ R_{3}\end {bmatrix} =P_{2}\begin {bmatrix} R_{2}\\ R_{1}\\ R_{3}\end {bmatrix} =\begin {bmatrix} R_{2}\\ R_{3}\\ R_{1}\end {bmatrix} \)
We see that the result is not the same. Hence in this example \(P_{1}P_{2}\neq P_{2}P_{1}\)
Now assume we have \(A=\begin {bmatrix} a\\ b\\ c\\ d \end {bmatrix} \), and let \(P_{3}\)be an exchange of the first and second rows, while \(P_{4}\) be an exchange of the third and 4th row. In this case we will see that \(P_{3}P_{4}=P_{4}P_{3}\)
: If \(P_{1}\) exchanges row \(i\) with row \(j,\)and \(P_{2}\) exchanges row \(k\) with row \(l.\) Then \(P_{1}P_{2}=P_{2}P_{1}\) only when \(i,j,k,l\) are all not equal. (not counting the trivial case when \(i=j\), \(k=l\))
Specific examples
\(P_{1}=\begin {bmatrix} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 0 & 1 \end {bmatrix} ,P_{2}=\begin {bmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end {bmatrix} \Rightarrow P_{1}P_{2}=\begin {bmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0 \end {bmatrix} \neq P_{2}P_{1}=\begin {bmatrix} 0 & 0 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end {bmatrix} \)
While
\(P_{3}=\begin {bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end {bmatrix} ,P_{4}=\begin {bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end {bmatrix} \Rightarrow P_{3}P_{4}=P_{4}P_{3}=\begin {bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end {bmatrix} \)