Math 272: Determinants and LU Decompositions

Names: 

You will work on this lab in pairs. When you have finished, save your file with the last names of everyone in your group, followed by Lab 3, e.g. NaqviTangLab3. Upload completed labs to Moodle: 
https://lms.ats.amherst.edu/mod/assign/view.php?id=353309
This lab is due 4:00pm on Tuesday, Feb 21.

I. Determinants

To compute a determinant in Mathematica, use the following commands:

A:={{1,2,0,4},{5,0,7,8},{9,10,11,12},{13,14,15,15}}
A//MatrixForm
Det[A]

(Remember that including “MatrixForm” in the first line as part of your definition of A will lead to errors! This command is only to tell Mathematica  to display the matrix.)

Important Theorem: A square matrix A is invertible if and only if det(A) is not zero.

Equation of line through two points

We want to find an equation ax+by+c=0 for the line through two given points (x1,y1) and (x2,y2).  

Plugging each point into the equation gives us 2 equations in 3 unknowns, a,b,c. Any other point (x,y) on this line also satisfies ax+by+c=0, which gives us a third equation, so that altogether we have:

ax+by+c=0
ax1+by1+c=0
ax2+by2+c=0

We want a,b,c not all equal to zero.  That is, we want a NONTRIVIAL solution to the HOMOGENEOUS system. 

Exercise 1.  Suppose we want the line to pass through the points (1,2) and (3,5).  Let X=(({{a}, {b}, {c}})) . 
Rewrite the system as a matrix equation AX=0 (treat x and y as coefficients of a and b; the matrix A should involve x, y, and numbers, but not a, b, or c).

Exercise 2.  What should the determinant of A equal, given that A is not invertible? (Remember that if A is invertible, the only possible solution is the trivial one.) Compute the determinant of A and set it equal to this value. This gives the equation of the line through (1,2) and (3,5). Verify your solution by plotting the equation using the ContourPlot command.

Parabola through three noncollinear points

Let's do a similar procedure to find the equation ax^2+bx+cy+d=0 for a parabola through noncollinear points (x1,y1), (x2,y2), and (x3,y3).

Exercise 3. Suppose we want the parabola to pass through (-1,6), (0,1), and (1,0).  Use these three points to generate three more equations.  Form a matrix equation of the original parabola equation in x and y plus the three equations from plugging in the points.

Exercise 4. We want a nontrivial solution to this homogeneous system AX=0, so again A is not invertible.  Simplify det A=0 to obtain the equation of the parabola through the three given points. Verify your solution by plotting the equation.

Circle determined by three noncollinear points

Exercise 5.  Use a similar procedure to find an equation a(x^2+y^2)+bx+cy+d=0 for the circle containing the points (-1,5), (2,2), and (-4,2).  What is the center and radius of this circle?  (Recall that a circle with radius R and center at (x0,y0) is described by (x-x0)^2+(y-y0)^2=R^2.) Verify your solution by plotting the equation.

II. LU-Decomposition

We have seen that matrices are invertible if and only if they are row equivalent to the identity matrix. However, we have seen that all matrices are row equivalent to an upper triangular matrix in row echelon form. 

 If A can be row-reduced to an upper triangular matrix U without using row swaps, then there is a sequence of lower triangular elementary matrices E1, ... , Ek such  that:

U = Ek ... E1 A

The inverse of each of these elementary matrices is also lower triangular. Let L1 be the inverse of E1, L2 be the inverse of E2, etc. Then

A = L1 ... Lk U

The product (L1 ... Lk) is also lower triangular, and we will denote it by L. Thus, A can be written as LU, where L is lower triangular and U is upper triangular. This is known as the LU Decomposition of A.

The LU decomposition makes it quite easy to solve systems of equations and find inverses. In fact, computer algebra systems like Mathematica use this rather than Gauss-Jordan elimination for many of its internal computations. Suppose we wish to decompose the following matrix:

A:={{3,6,-3},{6,15,-5},{-1,-2,6}}
A//MatrixForm

To perform our first row operation, we define an elementary matrix E1 that scales our first row by 1/3.

E1:={{1/3,0,0},{0,1,0},{0,0,1}}

To apply this to A, we compute the matrix product using the command E1.A

E1.A

We now clear the rows below our pivot position by defining two additional elementary matrices:

E2:={{1,0,0},{-6,1,0},{0,0,1}}
E3:={{1,0,0},{0,1,0},{1,0,1}}

Now apply these row operations as well to verify that we have an upper triangular matrix.

U:=E3.E2.E1.A

To find L, we need to compute the product of the inverses in the correct order.

L:=Inverse[E1].Inverse[E2].Inverse[E3]

Exercise 6. Verify that A=LU, det(A)=det(L)det(U), and (A^(-1))=(U^(-1))(L^(-1)).

Recall that this decomposition can be used for non-square matrices as well. In this case, L will still be square since it is a product of elementary matrices, but U will be the same shape as the original matrix.

Exercise 7. Find the LU decomposition of the following matrix A. (Remember to only use lower triangular elementary matrices! This means we only clear the column below pivot positions and ignore the entries above. After all, we’re only reducing to an upper triangular matrix, not a matrix in reduced row echelon form.)

A:={{1,-3,-2,0},{1,-2,1,-1},{2,-4,3,2}}

To solve equations of the form Ax=b, we observe that we have LUx=b. Let Ux=y. Then Ly=b, and we can solve for y starting at the first component and substituting each solved component into the subsequent equations. Since L is invertible, there is a unique solution for y. Next, we solve Ux=y by first finding the last component of x and substituting each solved component into the equations above.

Exercise 8. Use the LU decomposition from Exercise 7 to solve Ax=b for the vector b={3,11,9}.