Linear Algebra: Matrix Properties and System Solvers

Linear Algebra and Matrix Properties

1. State one property of a square matrix that will guarantee it is singular.
   There are many possibilities, some of which are: having determinant 0, having dependent columns, having dependent rows, and having a non-trivial null-space.
2. Can a system of linear equations have exactly 2 solutions?
   No, a system of linear equations can have either 0, 1, or infinitely many solutions.
3. What advantages does the Cholesky factorization have over Gaussian elimination?
   The Cholesky factorization only requires about half the operations of Gaussian elimination, and pivoting is never required for stability.
4. Can an n × n positive-definite matrix be singular? What about an n × n symmetric positive-definite matrix?
   The condition x^TAx > 0 implies that A must have a trivial null-space, so in both cases, the matrix is invertible.

Computational Cost of Linear Systems

Compare the computational cost (i.e., time complexity) of solving a system of linear equations Ax = b via Gaussian elimination with solving the same system by factoring A = LU and solving Ly = b and Ux = y. You do not need to give exact operations counts.

Both algorithms cost the same. The cost to compute the LU factorization is the same as the cost to perform forward elimination on the coefficient matrix. The only difference between these two is that we record the multipliers.

Similarly, both approaches must solve an upper-triangular system via back substitution at the final step, which will have the same cost. The only difference, then, is that Gaussian elimination also performs forward elimination on the right-hand side (via the augmented matrix), and LU factorization must solve Ly = b. In fact, because the diagonal of L contains only 1s, these require the same number of operations.

Least-Squares Solutions

1. Under what condition will the least-squares solution to an over-determined system exist?
   The least-squares solution is always guaranteed to exist.
2. Under what condition will the least-squares solution to an over-determined system be unique?
   There are many possible answers. Some acceptable answers include that the columns of the matrix are independent or that it is full rank.

Additional Questions

0

1. Under what condition will the least-squares solution to an over-determined system exist?
   The least-squares solution is always guaranteed to exist.
2. Under what condition will the least-squares solution to an over-determined system be unique?
   There are many possible answers. Some acceptable answers include that the columns of the matrix are independent or that it is full rank.