General

Prove something is a Subspace

Dimension of a Subspace

The dimension of a subspace is the size of an arbitrary basis. Find a basis of the subspace: We select elements $v_1,\dots ,v_k\in U$

1. Show the set is independent
2. Show the set generates the subspace Then the set is a basis. The dimension of $U$ is then $k$ the number of elements of the basis.

Example

See Sheet 6, exercise 5:

Determinant

The determinant only exists for square matrices!

Calculations

Least Squares

We solve the system of normal equations $A^{\top }Ax=A^{\top }b$ which boils down to using RREF on $[A^{\top }A|A^{\top }b]$ to find $\hat{x}$.

The solution is unique when $A$ has independent columns according to Theorem 6.11.

CR Decomposition

Proofs I (Vectors)

Prove a solution to some system exists with conditions

Use a matrix to model the system and add extra rows to model the extra conditions.

HS23 Proofs I c) has us show that there exists a $c$ such that … ${\mathbf{u}}^{\prime }:=\left[\begin{array}{c}{u}_1\\ u_2\\ 1\end{array}\right],{\mathbf{v}}^{\prime }:=\left[\begin{array}{c}{v}_1\\ v_2\\ 1\end{array}\right],{\mathbf{w}}^{\prime }:=\left[\begin{array}{c}{w}_1\\ w_2\\ 1\end{array}\right],{\mathbf{z}}^{\prime }:=\left[\begin{array}{c}{z}_1\\ z_2\\ 1\end{array}\right]$ We can add a row of 1s to the bottom of the solution matrix which makes them linearly dependent in ${\mathbb{R}}^3$ and thus there is a solution for $Ax=0$.

The bottom row correctly models the condition that $c_u+c_v+c_w+c_z=0$!

Prove something is a subspace

We have to prove the subspace is not empty (usually by showing the $0$ is in it). We have to prove that for $a,b\in U$, $a+b\in U$ and $\lambda a\in U$ for $\lambda \in \mathbb{R}$:

• closure under addition
• closure under scalar multiplication.

Show a set of vectors is a basis of some ${\mathbb{R}}^n$

Any $n$ linearly independent vectors are a basis of ${\mathbb{R}}^n$. (Script) We have our given vectors $v_1,v_2,\dots ,v_n$. We show that $w_1,w_2,\dots ,w_n$ is equal to the matrix product of $V$ (containing the $v$‘s) with some invertible matrix $M$ (such that $W=MV$). Thus we know $W$ is also invertible (as it’s the product of two invertible matrices, thus rank $n$) and therefore the $w$‘s span the space.

Proofs II

PD proofs

use th property PD ⇐> $x^{\top }Mx>0$. Then we multiply by $(Tv{)}^{\top }$ to use the PD of S and the PD of $T$ on the other side.

Make sure to try all possibilities which we can multiply by.

CR-Decomp and Pseudoinverse

We can use the CR decomposition to show things with the Pseudoinverse, if we need linearly independent rows/columns.

Find minimiser of some sum using Least Squares

See Exercise Sheet 8 Question 5.

We know System is unsolvable, use Certificate

If we get told a system like $Ax=b$ is unsolvable, we now know that the system $A^{\top }z=0$ and $b^{\top }z=1$ is solvable.

We use this to transform those two equations into $\left[\begin{array}{c}{A}^{\top }\\ b^{\top }\end{array}\right]z=\left(\begin{array}{c}0\\ 1\end{array}\right)$ which we know is solvable. And by the Lemma 6.2.2 this has a unique solution with $z\in R(\left[\begin{array}{c}{A}^{\top }\\ b^{\top }\end{array}\right])$. As $R(\left[\begin{array}{c}{A}^{\top }\\ b^{\top }\end{array}\right])=C({\left[\begin{array}{c}{A}^{\top }\\ b^{\top }\end{array}\right]}^{\top })=C(\left[\begin{array}{cc}A& b\end{array}\right])$.

Disprove something is a linear transformation

Use the unit-vectors and choose the correct linearity axiom to show (either multiplication or addition).

Then just insert them into the definition of the function and show that there’s a contradiction.

Show something about singular values

Try to bring the expression into either the form $A^{\top }A$ or $A{A}^{\top }$ and show that these matrices have some eigenvalue, the square root of which is then a singular value of $A$.

Note that something is only an eigenvector if $v\ne 0$!

We can also decompose into $A=U\Sigma V^{\top }$ Note that we can say that the singular values of $A^{-1}$ are $1/{\sigma }_1\le \cdots \le 1/{\sigma }_n$.

Multiple Choice

Use SVD and $A^{\top }A$ to show Singular Values

We have $A=v{w}^{\top }$ Then $A^{\top }A=(v{w}^{\top }{)}^{\top }(v{w}^{\top })=||v|{|}^{2}w{w}^{\top }$. We show that $w$ is an eigenvector using $A^{\top }Aw=||v|{|}^{2}w{w}^{\top }w=||v|{|}^2||w|{|}^{2}w$ with eigenvalue $\lambda =||v|{|}^2||w|{|}^2$. We know the singular values are the square-root of the eigenvalues of $A^{\top }A$ (or $A{A}^{\top }$). As $A^{\top }A$ has rank 1 (it’s $||v|{|}^{2}w{w}^{\top }$ ), this is the only eigenvalue.

Thus the only and biggest singular value of $A$ is $\sqrt{||v|{|}^2||w|{|}^2}=||v||||w||$.

Column Space of the Pseudoinverse

We know $A{A}^{†}$ is the projection matrix for projection onto $C(A)$. Thus $C(A{A}^{†})=C(A)$. Therefore $\dim (C(A{A}^{†}))=7-\dim (N(A{A}^{†}))$. We also have $N(A^{†})\subseteq N(A{A}^{†})$ thus $\text{rank}(A)=\dim (C(A{A}^{†}))=n-\dim (N(A{A}^{†}))\le n-\dim (N(A^{†}))=\text{rank}(A^{†})$We show the other direction $\text{rank}(A^{†})\le \text{rank}(A)$ in a symmetric argument.

Thus $\text{rank}(A)=\text{rank}(A^{†})$.

Eigenvalues of $AB$ are same as for $BA$

We have $ABv=\lambda v$ for $v\ne 0$.

• If $Bv=0$ then $B$ does not have full rank thus $BA$ also then $BA$ also has a $0$ EW.
• If $Bv\ne 0$ then $BA(Bv)=\lambda (Bv)$ thus $\lambda$ an EW of $BA$.