# ML Wiki

## Orthogonal Matrices

### Orthonormal Vectors

Vectors $\mathbf q_1, \ ... \ , \mathbf q_n$ are orthonormal if they are orthogonal and unit vectors

• $\mathbf q_i \; \bot \; \mathbf q_j \ \forall i \ne j$ and
• $\mathbf q_i^T \mathbf q_j = 0$ if $i \ne j$ and $\mathbf q_i^T \mathbf q_j = 1$ otherwise
• these vectors make a good basis

### Orthogonal Matrix

• The second part of the definition: $\mathbf q_i^T \mathbf q_j = \begin{cases} 1 & \text{if } i \ne j \\ 0 & \text{if } i = j \end{cases}$

• how do we put it in a matrix form?
• Consider a matrix $Q$ whose columns are vectors $\mathbf q_1, \ ... \ , \mathbf q_n$:
• let $Q = \Bigg[ \mathop{\mathbf q_1}\limits_|^| \ \mathop{\mathbf q_2}\limits_|^| \ \cdots \ \mathop{\mathbf q_n}\limits_|^| \Bigg]$
• $Q^T Q = \begin{bmatrix} - \ \mathbf q_1^T - \\ - \ \mathbf q_2^T - \\ \\ - \ \mathbf q_n^T - \end{bmatrix} \Bigg[ \mathop{\mathbf q_1}\limits_|^| \ \mathop{\mathbf q_2}\limits_|^| \ \cdots \ \mathop{\mathbf q_n}\limits_|^| \Bigg] = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ & & \ddots & \\  0 & 1 & \cdots & 1 \end{bmatrix}$ by our definition!

• so $Q^T Q = I$
• such $Q$'s are called Orthogonal Matrices

A matrix $Q$ is orthogonal if

• its columns are orthonormal vectors
• and it's square

• if $Q^T Q = I$, then $Q^T = Q^{-1}$

## Examples

### Identity Matrices

Identity matrices are orthogonal:

• $Q = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} = I$

• $Q^T Q = I I = I$

### Permutation Matrices

Permutation Matrices are orthogonal

• consider $Q = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{bmatrix}$

• then $Q^T = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{bmatrix}$ and indeed $Q^T Q = I$

• also note that $Q^T$ is also orthogonal

### Rotation Matrices

Rotation Matrices are also orthogonal

• let $Q = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \\ \end{bmatrix}$

• it's orthogonal

### Not Orthogonal Example

Not orthogonal:

• $S = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix}$

• why? $S^T S = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \\ \end{bmatrix}$

• how to fix it? they are not unit vectors, so need to normalize it:
• $Q = \cfrac{1}{\sqrt 2} \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix}$

• now $Q^T Q = \cfrac{1}{2} \begin{bmatrix} 2 & 0 \\ 0 & 2 \\ \end{bmatrix} = I$

• this one is orthogonal

## Usage

### Projection

Why is it good to have orthogonal matrices?

### Normal Equation

• $A^T A \mathbf{\hat x} = A^T \mathbf b$
• usual case (when $A$ is not orthogonal): $\mathbf{\hat x} = (A^T A)^{-1} A^T \mathbf b$
• orthogonal case: $\mathbf{\hat x} = (Q^T Q)^{-1} Q^T \mathbf b = Q^T \mathbf b$ - no inversion involved
• so can use $A = QR$ Factorization and get $\mathbf{\hat x} = R^{-1} Q^T \mathbf b$

### Factorizations

Orthogonal matrices are very nice because it's very easy to invert them

## Orthogonalization

How do we make matrices orthogonal?

Also,

• Eigendecomposition $A = Q \Lambda Q^T$ decomposes symmetric $A$ onto orthogonal $Q$ and diagonal $\Lambda$
• SVD $A = U \Sigma V^T$ decomposes $A$ onto orthogonal $U$ and $V$ and diagonal $\Sigma$

## Properties

### Transpose

If $Q$ is orthogonal matrix, then $Q^T$ is orthogonal as well

### Matrix Multiplication

If $Q_1$ and $Q_2$ are orthogonal, so is $Q_1 \cdot Q_2$

### Linear Transformation Properties

$Q$ preserves the $L_2$ norm:

• $\| Q \mathbf x \| = \| \mathbf x \|$
• proof: $\| Q \mathbf x \|^2 = (Q \mathbf x)^T (Q \mathbf x) = \mathbf x^T Q^T Q \mathbf x = \mathbf x^T \mathbf x = \| \mathbf x \|^2$

$Q$ preserves the angle between $\mathbf x$ and $\mathbf y$

• $\langle Q \mathbf x, Q \mathbf y \rangle = \langle \mathbf x, \mathbf y \rangle$
• proof: $(Q \mathbf x)^T (Q \mathbf y) = \mathbf x^T Q^T Q \mathbf y = \mathbf x^T \mathbf y$