Linear Algebra

Intro

Basic idea behind linear algebra: solving large number of linear algebraic equations simultaneously.

$ a_{i,1} x_1 + a_{i,2} x_2 + a_{i,3} x_3 + \dots + a_{i,N} x_{N} = b_{N} \qquad i=1 \dots M $

There are N unknowns and M equations, forming a linear system from matrices:

$ \mathbf{A \cdot x} = \mathbf{b} $

where lowercase letters denote vectors, and the dot represents multiplication of two matrices or a matrix and a vector, or dot product of two vectors.

Nonsingular vs Singular

We are not guaranteed to find a solution to a given linear system Ax=b

• row degeneracy - one or more of the M equations is a linear combination of other equations
• column degeneracy - one or more of the N variables are interchangeable and cannot be distinguished (are non-unique)
• for square matrices, these two conditions are equivalent

Having singular system of equations means we can't find good solutions.

Other things preventing good solution:

• Equations being equivalent to within roundoff error (approximately degenerate)
• Accumulation of roundoff error during solution can swamp solution

Many linear equation solving packages dedicate a good chunk of their code to solving these problems

Sense of scale:

• Linear equations with 20-50 unknowns are routine, can almost always be solved in single precision with straightforward routines
• Linear equations with up to 1,000 unknowns require double precision
• Larger sets of thousands or millions of equations can be solved with coefficients are sparse (mostly zero) by using specialty sparse methods

Tasks of Computational Linear Algebra

Beyond simply solving Ax=b for the unknowns x, we may want to do other things:

• Solve more than one matrix equation, $ \mathbf{A \cdot x}_j = \mathbf{b}_j $, where the matrix A does not change but unknown/RHS vectors do change
• Calculating the inverse of the matrix
• Calculating the determinant of a square matrix
• Calculating the condition number of a matrix

If M < N (row degeneracy), or if M = N and equations are degenerate, there are fewer equations than unknowns. If fewer equations than unknowns:

• Either no solution vector, or
• More than one solution vector
• If more than one solution, solution space consists of particular solution added to linear combination of N-M vectors (which are in the nullspace of the matrix A)
• SVD can be used to solve this problem, by find these vectors (SVD finds the nullspace of a matrix A)

If M > N (column degeneracy), there are fewer unknowns than equations. If fewer unknowns than equations:

• Think least squares - more data points than unknowns
• Looking for best fit/compromise solution
• Linear least-squares problem can be used to solve overdetermined linear system