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\)
\[ A=\begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 1 & 4 & 1 \end{bmatrix}\begin{bmatrix} 5 & 7 & 8\\ 0 & 2 & 3\\ 0 & 0 & 6 \end{bmatrix} =\allowbreak \begin{bmatrix} 5 & 7 & 8\\ 10 & 16 & 19\\ 5 & 15 & 26 \end{bmatrix} \]
Carry the first elimination, we get
\[ A=\allowbreak \begin{bmatrix} 5 & 7 & 8\\ 0 & 2 & 3\\ 0 & 8 & 18 \end{bmatrix} \]
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 \[ Ax=\begin{bmatrix} 2 & 3 & 3\\ 0 & 5 & 7\\ 6 & 9 & 8 \end{bmatrix}\begin{bmatrix} u\\ v\\ w \end{bmatrix} =\begin{bmatrix} 2\\ 2\\ 5 \end{bmatrix} \]
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 \begin{align*} L & =\begin{bmatrix} 1 & 0 & 0\\ l_{21} & 1 & 0\\ l_{31} & l_{32} & 1 \end{bmatrix} \\ & =\fbox{$\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 3 & 0 & 1 \end{bmatrix} $} \end{align*}
and \[ U=\fbox{$\begin{bmatrix} 2 & 3 & 3\\ 0 & 5 & 7\\ 0 & 0 & -1 \end{bmatrix} $}\]
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 \[ E^{n}=\begin{bmatrix} 1 & 0\\ n\times 6 & 1 \end{bmatrix} \]
Therefore
\begin{align*} E^{2} & =\begin{bmatrix} 1 & 0\\ 2\times 6 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 0\\ 12 & 1 \end{bmatrix} \\ E^{8} & =\begin{bmatrix} 1 & 0\\ 8\times 6 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 0\\ 48 & 1 \end{bmatrix} \\ E^{-1} & =\begin{bmatrix} 1 & 0\\ -1\times 6 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 0\\ -6 & 1 \end{bmatrix} \end{align*}
Problem: (a) Under what conditions is the following product non singular?
\[ A=\overset{L}{\overbrace{\begin{bmatrix} 1 & 0 & 0\\ -1 & 1 & 0\\ 0 & -1 & 1 \end{bmatrix} }}\overset{D}{\overbrace{\begin{bmatrix} d_{1} & 0 & 0\\ 0 & d_{2} & 0\\ 0 & 0 & d_{3}\end{bmatrix} }}\overset{V}{\overbrace{\begin{bmatrix} 1 & -1 & 0\\ 0 & 1 & -1\\ 0 & 0 & 1 \end{bmatrix} }}\]
(b) Solve the system \(Ax=b\) starting with \(Lc=b\)
\[ \overset{L}{\overbrace{\begin{bmatrix} 1 & 0 & 0\\ -1 & 1 & 0\\ 0 & -1 & 1 \end{bmatrix} }}\begin{bmatrix} c_{1}\\ c_{2}\\ c_{3}\end{bmatrix} =\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} =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)\begin{align*} Ax & =b\\ L\overset{c}{\overbrace{Ux}} & =b \end{align*}
\(Lc=b\) where \(Ux=c\)
hence starting with \(Lc=b\) we write
\[\begin{bmatrix} 1 & 0 & 0\\ -1 & 1 & 0\\ 0 & -1 & 1 \end{bmatrix}\begin{bmatrix} c_{1}\\ c_{2}\\ c_{3}\end{bmatrix} =\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} \]
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 \[ \left [ D\right ] \left [ V\right ] x=c \]\[ \overset{\left [ D\right ] \left [ V\right ] }{\overbrace{\begin{bmatrix} d_{1} & -d_{1} & 0\\ 0 & d_{2} & -d2\\ 0 & 0 & d_{3}\end{bmatrix} }}\begin{bmatrix} x_{1}\\ x_{2}\\ x_{3}\end{bmatrix} =\overset{c}{\overbrace{\begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} }}\]
Solve for \(x\) by back substitution process \(\Rightarrow \)\[ x_{3}=\frac{1}{d_{3}}\] 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 \begin{align*} x_{2} & =\left ( \frac{d_{2}}{d_{3}}\right ) \frac{1}{d_{2}}\\ & =\frac{1}{d_{3}} \end{align*}
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}}\)
\[\begin{bmatrix} x_{1}\\ x_{2}\\ x_{3}\end{bmatrix} =\begin{bmatrix} \frac{1}{d_{3}}\\ \frac{1}{d_{3}}\\ \frac{1}{d_{3}}\end{bmatrix} \]
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\)
\[ A=\begin{bmatrix} 1 & 0 & 1\\ 2 & 2 & 2\\ 3 & 4 & 5 \end{bmatrix} \]
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} \)
\begin{align*} L & =E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}=\overset{E_{21}^{-1}}{\overbrace{\begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} }}\overset{E_{31}^{-1}}{\overbrace{\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 3 & 0 & 1 \end{bmatrix} }}\overset{E_{32}^{-1}}{\overbrace{\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 2 & 1 \end{bmatrix} }}\\ & =\overset{E_{21}^{-1}}{\overbrace{\begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} }}\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 3 & 2 & 1 \end{bmatrix} \\ & =\overset{L}{\overbrace{\begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 3 & 2 & 1 \end{bmatrix} }} \end{align*}
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} \)