ZoomNotes for Linear Algebra

Part 2: Solving Linear Equations $Ax = b$ : $A$ is $n \times n$

2.1 Inverse Matrices $A^{-1}$ and Solutions $x = A^{-1}b$

If $A$ is a square invertible matrix, there exists $A^{-1}$ such that:

$$A^{-1}A = I \quad \text{and} \quad AA^{-1} = I$$

The solution to $Ax = b$ is then:

$$x = A^{-1}b$$

2x2 Inverse Formula:

$$\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}$$

Here $ad-bc$ is the determinant. If the determinant is zero, the matrix is singular (not invertible).

Conditions for Invertibility (all equivalent):

• Independent rows and independent columns
• Nonzero determinant
• No zero pivots during elimination
• $Ax = 0$ implies $x = 0$
• Full rank ($r = n$)

Inverse of a Product:

$$(AB)^{-1} = B^{-1} A^{-1}$$

Note the reverse order: the inverse of a product is the product of inverses in reverse order.

---

2.2 Triangular Matrix and Back Substitution for $Ux = c$

An upper triangular matrix $U$ has zeros below the diagonal:

$$U = \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{bmatrix}$$

Back Substitution solves $Ux = c$ starting from the last equation:

$$x_n = \frac{c_n}{u_{nn}}, \quad x_{n-1} = \frac{c_{n-1} - u_{n-1,n}x_n}{u_{n-1,n-1}}, \quad \dots$$

In general, for $i = n, n-1, \dots, 1$:

$$x_i = \frac{c_i - \sum_{j=i+1}^n u_{ij} x_j}{u_{ii}}$$

The pivots $u_{11}, u_{22}, \dots, u_{nn}$ must all be nonzero. A zero pivot means the system is singular (no unique solution).

---

2.3 Elimination: Square Matrix $A$ to Triangular $U$

Gaussian elimination transforms $A$ into an upper triangular matrix $U$ by subtracting multiples of rows from rows below.

The augmented matrix $[A \mid b]$ is carried to $[U \mid c]$ simultaneously.

Step-by-step for a 3x3 example:

1. Use row 1 (the pivot row) to eliminate the first entries of rows 2 and 3.
2. Use row 2 to eliminate the second entry of row 3.
3. The result is $U$, an upper triangular matrix.

The multiplier $\ell_{ij}$ is:

$$\ell_{ij} = \frac{\text{entry to eliminate}}{\text{pivot}}$$

Row $i$ $\leftarrow$ Row $i$ $- \ell_{ij} \times$ Row $j$

Pivots must be nonzero. If a pivot is zero, we attempt a row exchange. If all eligible rows have zero in the pivot position, the matrix is singular.

---

2.4 Row Exchanges for Nonzero Pivots: Permutation $P$

A permutation matrix $P$ has the rows of the identity matrix $I$ in any order. There are $n!$ permutation matrices of size $n \times n$.

Properties:

• $P^{-1} = P^T$ (permutation matrices are orthogonal)
• Multiplying $PA$ reorders the rows of $A$
• $P$ times a column vector reorders its entries

Example: The permutation that swaps rows 1 and 3:

$$P = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}$$

When a zero pivot is encountered during elimination, we exchange the current row with a lower row that has a nonzero entry in the pivot column. This means $PA = LU$, where $P$ encodes all the row swaps performed.

---

2.5 Elimination with No Row Exchanges: Why is $A = LU$?

When no row exchanges are needed, elimination factors $A$ into:

$$A = L U$$

• $L$ is lower triangular with 1's on the diagonal
• $U$ is upper triangular (the result of elimination)

Where do $L$ and $U$ come from?

Each elimination step subtracts $\ell_{ij} \times$ (pivot row $j$) from row $i$. This is equivalent to multiplying $A$ on the left by an elementary elimination matrix $E_{ij}$. The product of all $E_{ij}$ gives $U$:

$$E_{n,n-1} \cdots E_{31} E_{21} A = U$$

Then $A = (E_{21}^{-1} E_{31}^{-1} \cdots E_{n,n-1}^{-1}) U = L U$.

The entries of $L$ below the diagonal are the multipliers $\ell_{ij}$ themselves. The diagonal entries of $L$ are 1's.

Column-Row Multiplication View: $A = LU$ can also be seen as accumulating rank-one updates. Each step removes a rank-one matrix: (column $j$ of $L$) $\times$ (row $j$ of $U$).

---

2.6 Transposes / Symmetric Matrices / Dot Products

Transpose: The transpose $A^T$ has entries $(A^T)_{ij} = A_{ji}$. Rows become columns and vice versa.

Transpose Rules:

$$(A + B)^T = A^T + B^T, \quad (AB)^T = B^T A^T, \quad (A^{-1})^T = (A^T)^{-1}$$

Symmetric Matrices: $S = S^T$. For any matrix $A$, the products $A^T A$ and $A A^T$ are always symmetric:

$$(A^T A)^T = A^T (A^T)^T = A^T A$$

Dot Product as $x^T y$: The dot product $x \cdot y = x^T y = \sum x_i y_i$. This notation appears throughout linear algebra in applications involving work ($\text{force}^T \cdot \text{distance}$), income ($\text{prices}^T \cdot \text{quantities}$), and heat ($\text{temperatures}^T \cdot \text{entropy}$).

$LDL^T$ Factorization for Symmetric $S$: When $S$ is symmetric and elimination proceeds without row exchanges, we can write:

$$S = L D L^T$$

where $D$ is diagonal containing the pivots from $U$, and $L$ is lower triangular with 1's on the diagonal. This is a refinement of $LU$ that exploits symmetry, reducing storage and computation by roughly half.