$(1)$ In this question, you are asked to develop an algorithm for LU$-$factoring a symmetric linear

system.

$($a$)$ You are given a linear system $Ax=b,$A symmetric and non$-$singular. Prove that Gauss

elimination without pivoting $($which is the name of the $LU-$factorization algorithm we studied in

class$)$ preserves the symmetry of $A$ in the following sense: after $j$ elimination steps, the $(m-j)$

$(m-j)$ lower right portion of $A_j$ is still symmetric, i$.$e$.,$ the matrix

$A_j(j+1$:$m,j+1$:$m)$

is symmetric. $($Hint: do a small example to see what happens.$)$

$($b$)$ Use $($a$)$ in order to modify the Gauss elimination method for $LU$ factorization for a symmetric

$A.$ Your new algorithm should obtain the correct $L$ and $U$ without modifying the elements of $A$

below the diagonal. Write a Matlab code for that algorithm. Submit a well$-$documented printout

of your code and explain $($on a separate sheet$),$ how you avoided processing the lower portion of

the matrix.

Hint: We learned in class to perform the $j\text{'}$th elimination step as

$A_{j-1}{A}_j=A_{j-1}+l_j{e}_j^{\text{'}}{A}_{j-1}.$

You might not be able to write your new algorithm in such compact format. So$,$ first thing, compute

the rank$-1$ matrix $l_j(e_j^{\text{'}}{A}_{j-1})$ entry$-$by$-$entry using two loops. Your new algorithm can then modify

the two loop code.

$($c$)$ Find the complexity of your algorithm $($remember that the complexity of Gauss elimination for

general matrices is $\{$:$\frac{m^3}{3}).$

$($d$)$ Test your observation in $($c$)$: run your algorithm on $2-3$ examples of symmetric matrices of

different sizes, and run on those matrices the Gauss elimination algorithm before you modified it

for symmetric matrices. Check the tic$-$toc count for each run $($run tic$-$toc about $100$ times and

average in order to get a reliable reading$)$ and compare. Compare your experiment here with your

analysis in $($c$).$