When do we use eigenvectors?

• these usually show up when we’re dealing with matrix inequalities, like $A \succeq 0$. In this case, it is equivalent to checking if $\lambda_{\min}(A) \geq 0$.

• If we add $\lambda I$ to a matrix, we add $\lambda$ to its eigenvalues

Definitiveness

A matrix is positive definite if $x^TAx > 0$, and positive semidefinite if $x^TAx \geq 0$.

PSD does not necessarily imply that it is symmetric, although we often restrict our discussions to symmetric matrices

These things are equivalent for PSD (and therefore are necessary & sufficient conditions)

• $x^TAx \geq 0$
  • element tool: use summation expansion
  • vector tool: look for norms

• Eigenvectors non-negative
  • vector tool: look for some norm contradiction
  • No guarantees that there is an eigenbasis though (although if it’s symmetric, it does have eigenbasis)

• $A = R^TR$ for some matrix $R$. Proof: take SVD, things cancel out, and you get a new SVD and each of the singular values are positive because they are squared). s

Other important properties for PSD (necessary, but not sufficient)

• invertible if positive definite (because there exists no vector that gets crushed to zero)

• If invertible (non-zero eigenvectors), the inverse of PSD is also PSD. Proof: assuming that it’s symmetric, you can invert it by taking the reciprocal of eigenvalues, which maintains positive

• determinant is always positive

Inverses

Sufficient conditions (cheat sheet)

Here are some sufficient conditions

• eigenbasis with non-zero eigenvalues

• Positive definite + symmetric (symmetric guarantees eigenbasis, positive definite guarantees that all eigenvalues are positive)

• No null space

Pseudoinverse (moore Penrose)

One easiest way of undersatnding the pseudoinverse is that it solves $||Ax - b||_2^2$ by setting $x = A^+b$.

But more concretely, the pseudoinverse does two things

1. Projects the output onto the range of $A$

2. Moves this back into the non-null space of $A$

This is not necessarily the true inverse, because the input could have had a component in the null space of $A$, which is forever lost. The best input may not reach $b$, because it may be outside of the range of $A$. So this part is lost too.

We can compute the inverse by doing SVD and doing the reciprocal of the $\Sigma$ unless it’s zero. In that case, just put in a zero.

Symmetric matrices

$A = A^T$ is a symmetric matrix. $A = -A^T$ is an antisymmetric matrix. All symmetric and antisymmetric matrices are square.

Symmetric

The sufficient condition is that $A = A^T$.

If a matrix is symmetric, this means that

1. Can be decomposed into $U\Sigma U^T$ where $U$ is the the eigenbasis (spectral theorem)

2. Has orthogonal eigenbasis (spectral theorem)

3. Can be factored into $VV^T$. If $\Sigma$ is non-negative, the $V$ is real (derived from the factorization)

4. Inverse is also symmetric

Note that symmetry does not guarentee invertibility as the eigenbasis may have eigenvalues of $0$.

Side note: if a matrix is not symmetric, it can still be decomposed through SVD.

Sums of symmetric matrices

$A + A^T$ is symmetric and $A - A^T$ is antisymmetric. Furthermore, because $A = \frac{1}{2} (A + A^T) + \frac{1}{2}(A - A^T)$, we can express any matrix $A$ as the sum of a symmetric and an antisymmetric matrix!!

Numerical methods

Flop Count, BLAS

A FLOP is a floating point operation, and

Different linear algebra operations have different flop counts

• Blas level 1 is vector-vector, and usually it’s O(n)

• Blas level 2 is matrix-vector, and tyis is typically O(mn) when we have an m x n matrix

• Blas level 3 is matrix-matrixi, and this is usually O(mnp) where we have an m x n matrix and a n x p matrix.
  • possible to reduce complexity if we are sparse

Systems of linear equations

If $A$ is invertible, then the solution to $Ax = b$ is just $A^{-1}b$. However, we almost never take the inverse directly because it is $O(n^3)$. There are other ways of implicitly computing the inverse.

Diagonal matrices are trivial to compute the inverse, and triangular matrices can be computed through forward substitution.

Orthogonal matrices are easy to invert, and permutation matrices are also trivial to invert because they are orthogonal. In fact, because permutation matrices are just ones and zeros, we can just read the permutations differently, so the cost of solving the equation is 0 flops; there is no computations needed.

If you can factor the matrix into simpler matrices, then you can invert each one individually. Sometimes if you do it correctly, the complexity drops. This is especially helpful if you want to solve $Ax = b$ for multiple $b$’s. A common factorization is $A = PLU$, where L is lower-triangular and U is upper-triangular. This is around $O((2/3)n^3)$ for large $n$. We can also factor the matrix through Cholesky factorization of $A = LL^T$ if $A$ is PSD. Here, $L$ is lower triangular with positive diagonals.

Block Elimination

You can express $Ax = b$ as a block equation

And we can write $x_1$ as

which allows us to write the following

We call

the Shur complement.

• Algorithm