Matrix Operations

1. Matrix Multiplication
   • Note that the inner dimensions need to match up
2. Transpose
   • $A_{ij}=A_{ji}^T$, this means swap the rows and the columns
3. Inverse
   • $A{A}^{-1}=I=A^{-1}A$
   • Not all matrices have an inverse
   • The following statements are equivalent
     • A is invertible
     • The rank of A is n
     • RREF of A is the identity matrix
     • For all $b\in {\mathbb{R}}^n$ the system $Ax=b$ has a unique solution
     • The columns of A are linearly independent
     • The column space of A is ${\mathbb{R}}^n$
   • The way you find the inverse depends on the size of the matrix but for a simple 2x2 matrix…
   • $A^{-1}=\frac{1}{(ad-bc)}\left[\begin{array}{ccc}d& & -b\\ -c& & a\end{array}\right]$

Some properties include…

1. $(AB{)}^T=B^T{A}^T$
2. $(A+B{)}^T=A^T+B^T$
3. $(tA{)}^{-1}=\frac{1}{t}{A}^{-1}$
4. $(AB{)}^{-1}=A^{-1}{B}^{-1}$

More On Matrix Multiplication

If we want to compute the product of 2 $n\times n$ matrices $X$ and $Y$ which is $Z=X\times Y$. The $(i,j)$ entry is… $Z_{ij}={\sum }_{k=1}^n{X}_{ik}{Y}_{kj}$ where we just perform a dot product of the $ith$ row of $X$ and $jth$ columns of $Y$.

There are $n^2$ entries to compute here ($Z_{ij}$). Assuming each entry is independent of n $Z_{ij}$ requires $n-1$ additions and $n$ multiplications. Therefore, directly computing $Z$ takes $O(n^3)$ time.
There is a better way to do this using Divide and Conquer.
Let’s divide $X$ and $Y$ into four $\frac{n}{2}$ by $\frac{n}{2}$ blocks. This looks like $X=\left[\begin{array}{ccc}A& & B\\ C& & D\end{array}\right]$ and $Y=\left[\begin{array}{ccc}E& & F\\ G& & H\end{array}\right]$. Here, the multiplication is expressed as…
$XY=\left[\begin{array}{ccc}AE+BG& & AF+BH\\ CE+DG& & CF+DH\end{array}\right]=\left[\begin{array}{ccccc}{P}_5+P_4-P_2+P_6& & P_1+P_2& & \\ P_3+P_4& & P_1+P_5-P_3-P_7& & \end{array}\right]$

Where:

• $P_1=A(F-H)$
• $P_2=(A+B)H$
• $P_3=(C+D)E$
• $P_4=D(G-E)$
• $P_5=(A+D)(E+H)$
• $P_6=(B-D)(G+H)$
• $P_7=(A-C)(E+F)$ This decomposition is called Strassen’s Algorithm. This allows us to compute $XY$ using 7 $\frac{n}{2}\times \frac{n}{2}$ matrix multiplications instead of 8.

The recurrance relation for the run-time is: $T(n)=7T(\frac{n}{2})+O(n^2)$. From master’s theorem, we get $T(n)=O(n^{{\log }_{2}7})$ which is about $n^{2.81}$.