\documentclass[12pt]{article}
\input{../macros.tex}
\begin{document}

\thispagestyle{plain}

\setcounter{session}{4}
\begin{center}
\textbf{Exercises on factorization into $\mb A = \mb L \mb U$}
\end{center}

\begin{problem} What matrix $E$ puts $A$ into triangular form $EA = U$? Multiply by $E^{-1} = L$ to factor $A$ into $LU.$

\vspace{10pt}

$$A = \threebythree
1 3 0 
2 4 0 
2 0 1 $$
\end{problem}

\solution{ We will perform a series of row operations to transform the matrix $A$ into an upper triangular matrix. First, we multiply the first row by 2 and then subtract it from the second row in order to make the first element of the second row 0:

$$\threebythree 1 0 0 {-2} 1 0  0 0 1 \threebythree 1 3 0 2 4 0 2 0 1 = \threebythree 1 3 0 0 {-2} 0 2 0 1 $$

\medskip

\noindent Next, we multiply the first row by 2 (again) and subtract it from the third row in order to make the first element of the third row 0:

$$\threebythree 1 0 0 0 1 0 {-2} 0 1 \threebythree 1 3 0 0 {-2} 0 2 0 1 = \threebythree 1 3 0 0 {-2} 0 0 {-6} 1$$

\medskip

 Now, we multiply the second row by 3 and subtract it from the third row in order to make the second element of the third row 0:

$$\threebythree 1 0 0 0 1 0  0 {-3} 1 \threebythree 1 3 0 0 {-2} 0 0 {-6} 1 = \threebythree 1 3 0 0 {-2} 0 0 0 1 = U.$$ 

\medskip

\noindent We take the three matrices we used to perform each operation and multiply them to get $E$:

$$E = \threebythree 1 0 0 0 1 0  0 {-3} 1 \threebythree 1 0 0 0 1 0 {-2} 0 1 \threebythree 1 0 0 {-2} 1 0  0 0 1  $$

$$ = \threebythree 1 0 0 0 1 0  0 {-3} 1 \threebythree 1 0 0 {-2} 1 0 {-2} 0 1   = \threebythree 1 0 0 {-2} 1 0 4 {-3} 1 = E.$$

\medskip

\noindent To check, we evaluate $EA$:
 
$$\threebythree 1 0 0 {-2} 1 0 4 {-3} 1 \threebythree
1 3 0 
2 4 0 
2 0 1 = \threebythree 1 3 0 0 {-2} 0 0 0 1= U. $$

\medskip

\noindent To find $E^{-1},$ use the Gauss-Jordan elimination method (or just insert the multipliers 2, 2, 3 into $E^{-1}$) 

$$ \left [ \begin{array}{rrr|rrr}
1 & 0 & 0 &  1 & 0 & 0 \\
-2 & 1 & 0 & 0 & 1 & 0 \\
4 & -3 & 1 & 0 & 0& 1 
\end{array} \right ] \longrightarrow \left [ \begin{array}{rrr|rrr}
1 & 0 & 0 &  1 & 0 & 0 \\
0 & 1 & 0 & 2 & 1 & 0 \\
0 & -3 & 1 & -4 & 0& 1 
\end{array} \right ]$$

\medskip

$$\longrightarrow \left [ \begin{array}{rrr|rrr}
1 & 0 & 0 &  1 & 0 & 0 \\
0 & 1 & 0 & 2 & 1 & 0 \\
0 & 0 & 1 & 2 & 3& 1 
\end{array} \right ] \longrightarrow \threebythree 1 0 0 2 1 0 2 3 1 = E^{-1}$$

\medskip

\noindent We can check that this is in fact the inverse of $E$:

$$E E^{-1} = \threebythree 1 0 0 {-2} 1 0 4 {-3} 1  \threebythree 1 0 0 2 1 0 2 3 1  = \threebythree 1 0 0 0 1 0 0 0 1 = I. $$

\medskip

\noindent Finally, to factorize $A$ into $LU$ (where $L = E^{-1}$):

$$\threebythree
1 3 0 
2 4 0 
2 0 1 = A = LU = \threebythree 1 0 0 2 1 0 2 3 1 \threebythree 1 3 0 0 {-2} 0 0 0 1. $$
}


\begin{problem}
(2.6 \#13.  {\em Introduction to Linear Algebra:} Strang) Compute $L$ and $U$ for the symmetric matrix 

$$\vb A = \left [ \begin{array}{cccc} 
a & a & a & a \\
a  & b & b & b \\
a  & b & c & c \\
a  & b & c & d \\  \end{array} \right ].  $$

\noindent Find four conditions on $a,b,c,d$ to get $A = LU$ with four pivots.
\end{problem}

\solution{
Elimination subtracts row 1 from rows 2-4, then row 2 from rows 3-4, and finally row 3 from row 4; the result is $U$. All the multipliers $\ell_{ij}$ are equal to 1; so $L$ is the lower triangular matrix with 1's on the diagonal and below it.

$$\vb A \longrightarrow  \left [ \begin{array}{cccc} 
a & a & a & a \\
0 & b-a & b-a & b-a \\
0 & b-a & c-a & c-a \\
0 & b-a & c-a & d-a \\  \end{array} \right ]  
 \longrightarrow 
 \left [ \begin{array}{cccc} 
a & a & a & a \\
0 & b-a & b-a & b-a \\
0 & 0 & c-b & c-b \\
0 & 0 & c-b & d-b \\  \end{array} \right ] $$

$$\longrightarrow \left [ \begin{array}{cccc} 
a & a & a & a \\
0 & b-a & b-a & b-a \\
0 & 0 & c-b & c-b \\
0 & 0 & 0 & d-c \\  \end{array} \right ]  
 = U, L = 
 \left [ \begin{array}{cccc} 
1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 \\
1 & 1 & 1 & 1 \\  \end{array} \right ].$$

The pivots are the nonzero entries on the diagonal of $U$. So there are four pivots when these four conditions are satisfied: $a \neq 0, b \neq a, c \neq b,$ and $d \neq c.$  
}
\end{document}