In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. By contrast, if most of the elements are nonzero, then the matrix is considered dense. The number of zero-valued elements divided by the total number of elements (e.g., m × n for an m × n matrix) is called the sparsity of the matrix (which is equal to 1 minus the density of the matrix). Using those definitions, a matrix will be sparse when its sparsity is greater than 0.5.
Hermitian, symmetric, triangular, tridiagonal, or bidiagonal
Elimination = Factorization: A=LU
L is a lower triangular product of elimination inverse and it contains the numbers lij. i.e. We want to factor A, not U.
The key reason why A=LU:
E−1 and E are lower triangular. Its off-diagonal entry is lij the undo the subtraction produced by −lij. The main diagonals contain 1's.
LDU. Lower triangular L times diagonal D times upper triangular U.
One square system.
A band matrix B has w nonzero diagonals below and above its main diagonal.
Factor: O(n3) to O(nw2). Solve: O(n2) to O(2nw).
Most matrices in practice are sparce (many zero entries). In that case A=LU is much faster.
n=103. 1 second.
n=104. 103 seconds.
n=105. 106 seconds.
This is too expensive without a supercomputer, but that these matrices are full. Most matrices in practice are sparse (many zero entries). In that case, A=LU is much faster.
Transposes and Permutations
If B is a vector x, such that
If B is [x1x2...], such that
The meaning of Inner Products
T is inside. The dot product or inner product is xTy=x⋅y=number=<x∣y> (1xn)(1xn)
T is outside. The rank one product or outer product is xyT=∣x><y∣=matrix (nx1)(1xn)
These are the most important matrices of all.
Definition. A permutation matrix P has the rows of the identity I in any order
Single 1 in every row and every column. There are n! permutation matrices of order n.
If A is invertible then a permutation P will reorder its rows for
ATA=0 and A=0 is impossible.
Find P3x33=I (but not P = I)
3. Find P4x44=I
4. Prove that the identity matrix cannot be te product of three row exchanges (or five). It can be the product of two exchanges (or four).
We have a permutation matrix Ep with only two rows distinct to I. It represents a row exchange.
This the highest level of understating about matrix calculations.
DEFINITION. The standard n-dimensional space Rn consists of all column vectors v with n real components.
The "vectors" in S can be matrices or functions of x.
M (2 by 2 matrices) and F (functions) and Z (zero vector alone) are vector spaces.
Max-plus vector space
An interesting “max-plus” vector space comes from the real numbers R combined with −∞. Change addition to give x + y = max(x, y) and change multiplication to
xy = usual x + y. Which y is the zero vector that gives x+0 = max(x, 0) = x for every x?
DEFINITION. A subspace of a vector space is a set of vectors (incluiding 0) that two requirements:
If v and w are vectors in the subspace and c is any scalar, then
v+w is in the subspace.
cv is in the subspace.
The smallest subspace
The linear span (also called the linear hull or just span) of a set S of vectors in a vector space is the smallest linear subspace that contains the set.
C(A) is a combination of r (number of pivots) columns.