EECS 445: Introduction to Machine Learning

Hands-On Lecture 2: Linear Algebra

Wednesday, September 14, 2016

Outline

This hands-on lecture corresponds to material from Lecture 02: Linear Algebra & Optimization.

Advice: Interpreting Matrix Operations (10-15mins)

Matrix-vector multiplication
Problem 1: Image of a matrix
Matrix-matrix multiplication

Hands-on Exercises (60mins)

Problem 2: Matrix Transpose
Problem 3: Infinity Norm
Problem 4: Matrix Inverse
Problem 5: Singular Values

Advice: Interpreting Matrix Operations

Think of matrix operations in terms of row- and column-vectors, rather than in terms of individual entries.

This section borrows material heavily from the first chapter of Trefethen & Bau, ["Numerical Linear Algebra"](http://bookstore.siam.org/ot50/)

Advice: Matrix-Vector Multiplication (Row View)

Recall the following definition of matrix multiplication:

If $x \in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$, then the $i$th entry of $b = Ax \in \mathbb{R}^m$ is:

$$ b_i = \sum_{j=1}^n a_{ij} x_j \quad (i = 1,\dots,m) $$

In other words, $b$ is a dot product between $x$ and the rows of $A$. If you think of $A$ as data matrix, it is useful to keep in mind the following interpretation:

Each row of $A$ is "scored" based on how well it aligns with the vector $x$.

Advice: Matrix-Vector Multiplication (Column View)

An alternative interpretation that comes handy when you want to study the subspaces of matrix is:

If $b = Ax$, then $b$ is a linear combination of the columns of $A$, with coefficients from the vector $x$.

Problem 1: Range and Nullspace

Recall that the range or image of $A \in \mathbb{R}^{m \times n}$ is the set of vectors $y \in \mathbb{R}^m$ that can be written as $y=Ax$ for some $x \in \mathbb{R}^n$,

$$ \text{im} \hspace{0.1cm} \text{A} = \{ y \in \mathbb{R}^m \mid \exists x \in \mathbb{R}^n, y = Ax \} $$

**Problem 1:** Argue that $\text{im} \hspace{0.1cm} \text{A}$ is the space spanned by the columns of $A$.

Hint: Use our "column view" of matrix-vector multiplication!

Solution 1: Range and Nullspace

**Problem 1:** Argue that $\text{im} \hspace{0.1cm} \text{A}$ is the space spanned by the columns of $A$.

Because any $Ax$ is a linear combination of the columns of $A$, any vector $y \in \text{im} \hspace{0.1cm} \text{A}$ can be written as a linear combination of the columns of $A$, $$ y = \sum_{j=1}^n x_j a_j $$ Forming a vector $x \in \mathbb{R}^n$ out of these coefficients $x_j$, we have $y = Ax$, and thus $y \in \text{im} \hspace{0.1cm} \text{A}$.

Advice: Matrix-Matrix Multiplication

The formula for matrix-matrix multiplication probably scares you a little:

If $A \in \mathbb{R}^{\ell \times m}$ and $C \in \mathbb{R}^{m \times n}$, then $B = AC \in \mathbb{R}^{\ell \times n}$ with entries

$$ b_{ij} = \sum_{k=1}^m a_{ik} c_{kj} $$

Advice: Matrix-Matrix Multiplication

If $B = AC$, then *each column of $B$ is a linear combination of the columns of $A$* with coefficients from the columns of $C$.

$$ \boxed{ b_j = A c_j } $$

Problem 2: Multiplication by Triangular Matrix

**Problem 2:** Consider $B = AR$, where $R$ an upper-triangular matrix with entires all equal to one on and above the diagonal. Interpret the columns of $B$ using our new interpretation of matrix multiplication.

Solution 2: Multiplication by Triangular Matrix

Since $B=AR$, the columns of $B$ are linear combinations of the columns of $A$, with coefficients taken from the columns of $R$. Because of the diagonal structure of $R$, the $j$th column of $B$ is the sum of the first $j$ columns of $A$:

$$ b_j = A r_j = \sum_{k=1}^j a_j $$

Advice: Conclusion

If you hadn't seen these interpretations before, they may seem a little strange. Keep at it! Thinking about linear algebra in this way will help a lot in the long run.

Hands-on Exercises

Review: Matrix Transposition

Recall that the transpose of $A \in \mathbb{R}^{m \times n}$ is $A^T \in \mathbb{R}^{n \times m}$ with indeces "flipped", $$ (A^T)_{ij} = A_{ji} $$

Transposition flips entries across the diagonal
Transposition turns rows into columns and vice-versa
A matrix is symmetric if $A^T = A$.

Problem 3.1: Matrix Transpose

**Problem 3.1:** Let $A$ and $B$ be two matrices compatible with multiplication. Is it true that $AB = A^T B^T$? Either prove or give a counterexample.

Solution 3.1: Matrix Transpose

**Problem 3.1:** Let $A, B \in \mathbb{R}^{n \times n}$ Is it true that $AB = A^T B^T$? Either prove it or give a counterexample.

False. Let $A \in \mathbb{R}^{n \times n}$ be any square matrix and $B = I$ be the identity. Unless $A$ is symmetric, then $AB = A \neq A^T = A^TB^T$. There are plenty of asymmetric matrices! For example,

$$ A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} $$

Problem 3.2: Matrix Transpose

**Problem 3.2:** Is it true that $(AB)^T = B^T A^T$? Either prove it or give a counterexample.

Solution 3.2: Matrix Transpose

**Problem 3.2:** Is it true that $(AB)^T = B^T A^T$? Either prove it or give a counterexample.

True! Assume $A \in \mathbb{R}^{m \times p}, B \in \mathbb{R}^{p \times n}$. After verifying that the matrix dimensions match up, we can verify it the brute-force way,

$$ \begin{aligned} [(AB)^T]_{ij} &= [AB]_{ji} = \sum_{k=1}^p a_{jk} b_{ki} \\ [B^TA^T]_{ij} &= \sum_{k=1}^p [B^T]_{ik} [A^T]_{kj} = \sum_{k=1}^p a_{jk} b_{ki} \end{aligned} $$

Try to interpret this result using what we've learned about matrix-vector products!

Problem 3.3: Matrix Transpose

**Problem 3.3:** Prove that $A+A^T$, $A^TA$, and $AA^T$ are all symmetric.

Solution 3.3: Matrix Transpose

**Problem 3.3:** Prove that $A+A^T$, $A^TA$, and $AA^T$ are all symmetric.

Verify the first one elementwise:

$[(A+A^T)^T]_{ij} = [A + A^T]_{ji} = [A]_{ij} + [A]_{ji} = [A+A^T]_{ij}$

Use Problem 3.2 to solve the other two:

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

Problem 4: Matrix Inverse

**Problem 4:** Let $A$ and $B$ be two $n \times n$ matrices. Prove, or find a counterexample, to the statement that $$ (AB)^{-1} = B^{-1} A^{-1} $$

Solution 4: Matrix Inverse

**Problem 4:** Let $A$ and $B$ be two $n \times n$ matrices. Prove, or find a counterexample, to the statement that $$ (AB)^{-1} = B^{-1} A^{-1} $$

Solution 4: Recall that, for any matrix $M$, the inverse $M^{-1}$ is the unique matrix such that $MM^{-1} = I$, the identity matrix.

...

Problem 4: Infinity Norm

**Problem 4:** Prove that the infinity norm $||x||_\infty = \max_k |x_k|$ is indeed a norm for $x \in \mathbb{R}^n$.

Recall that $|| \cdot || : \mathbb{R}^n \rightarrow \mathbb{R}$ is a norm if and only if for all $x,y \in \mathbb{R}^n$ and $\alpha \in \mathbb{R}$,

$|| x || \geq 0$
$||x||=0$ if and only if $x = 0$.
$|| \alpha x || = |\alpha| ||x||$ (Homogeneity)
$|| x + y || \leq ||x|| + ||y||$ (Triangle Inequality)