## Problem Set 1

#### Part 1

Show that $$A^TA \neq AA^T$$ in general. (Proof and demonstration.)

Assume $$A^T A = A A^T$$ Consider matrix $$A_{m\times n}$$ where $$m \ne n$$. So $$A^T$$ will be the size of $$n \times m$$. Also $$AA^T$$ will be a matrix of size $$m\times m$$ and $$A^TA$$ will be a matrix of size $$n \times n$$.

Since $$m \ne n$$, clearly these two matrices will not be equal. This is clearly a contradiction for all non-square matrix. But what about square matrices where $$m = n$$. Let’s see!

Continue with this, consider a simple square matrix $$A_{2\times 2}$$.

Let $$A= \left[ \begin{array}{cccc} a & b \\ c & d \\ \end{array} \right] \\$$

$$A^T = \left[ \begin{array}{cccc} a & c \\ b & d \\ \end{array} \right] \\$$

$$AA^T = \left[ \begin{array}{cccc} a^2+b^2 & ac+bd \\ ac+bd & c^2+cd \\ \end{array} \right] \\$$

$$A^TA = \left[ \begin{array}{cccc} a^2+b^2 & ab+cd \\ ab+cd & b^2+d^2 \\ \end{array} \right] \\$$

Clearly, it’s not always true $$\forall a,b,c,d$$. Therefore we conclude that $$A^TA \neq AA^T$$ .

#### Part 2

For a special type of square matrix A, we get AT $$A^TA = AA^T$$ . Under what conditions could this be true? (Hint: The Identity matrix I is an example of such a matrix).

This condition is true if and only if $$A = A^T$$. Transposing a matrix switches columns into rows, i.e. flips the values along the diagonal.

The condition $$A^T = A$$ holds if the matrix is symmerical along the diagonal, just like the identity is.

Example - consider the following symetric matrix A:

$$A = \left[ \begin{array}{cccc} 1 & 2 \\ 2 & 3 \\ \end{array} \right] \\$$

A <- matrix(c(1,2,2,3), ncol = 2)
#transpose of A
AT <- t(A)
write('Printing A:', stdout())
## Printing A:
A
##      [,1] [,2]
## [1,]    1    2
## [2,]    2    3
write('Printing AT:', stdout())
## Printing AT:
AT
##      [,1] [,2]
## [1,]    1    2
## [2,]    2    3
write('Printing A*AT', stdout())
## Printing A*AT
A%*%AT
##      [,1] [,2]
## [1,]    5    8
## [2,]    8   13
write('Printing AT*A:', stdout())
## Printing AT*A:
AT %*% A
##      [,1] [,2]
## [1,]    5    8
## [2,]    8   13

## Problem Set 2

Matrix factorization is a very important problem. There are supercomputers built just to do matrix factorizations. Every second you are on an airplane, matrices are being factorized. Radars that track flights use a technique called Kalman filtering. At the heart of Kalman Filtering is a Matrix Factorization operation. Kalman Filters are solving linear systems of equations when they track your flight using radars. Write an R function to factorize a square matrix A into LU or LDU, whichever youprefer. Please submit your response in an R Markdown document using our class naming convention, E.g. LFulton_Assignment2_PS2.png. You don’t have to worry about permuting rows of A and you can assume that A is less than 5x5, if you need to hard-code any variables in your code. If you doing the entire assignment in R, then please submit only one markdown document for both the problems.

factorizeThis <- function(M) {
dimentions <- dim(M)

# check for square matrix
if (dimentions[1] != dimentions[2]) return(NA)

U <- M
n <- dimentions[1]
L <- diag(n)

# if dim is 1, the U=A and L=[1]
if (n == 1) return(list(L, U))

# loop through lower triangle
# determine multiplier
for(i in 2:n) {
for(j in 1:(i - 1)) {
multiplier <- -U[i, j] / U[j, j]
U[i, ] <- multiplier * U[j, ] + U[i, ]
L[i, j] <- -multiplier
}
}
return(list('L' = L, 'U' = U))
}

### Test our function

using this matrix:

$$A = \left[ \begin{array}{cccc} 1 & 4 & -3 \\ -2 & 8 & 5 \\ 3 & 4 & 7 \\ \end{array} \right] \\$$

A <- matrix(c(1,-2,3,4,8,4,-3,5,7), ncol = 3)

a <- factorizeThis(A)

write('Printing A:', stdout())
## Printing A:
A
##      [,1] [,2] [,3]
## [1,]    1    4   -3
## [2,]   -2    8    5
## [3,]    3    4    7
write('Printing Lower Triangular Matrix L:', stdout())
## Printing Lower Triangular Matrix L:
a$L ## [,1] [,2] [,3] ## [1,] 1 0.0 0 ## [2,] -2 1.0 0 ## [3,] 3 -0.5 1 write('Printing Upper Triangular Matrix U:', stdout()) ## Printing Upper Triangular Matrix U: a$U
##      [,1] [,2] [,3]
## [1,]    1    4 -3.0
## [2,]    0   16 -1.0
## [3,]    0    0 15.5

Trying another one:

$$B = \left[ \begin{array}{cccc} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \\ \end{array} \right] \\$$

B <- matrix(seq(1, 9), nrow = 3)

b <- factorizeThis(B)

write('Printing B:', stdout())
## Printing B:
B
##      [,1] [,2] [,3]
## [1,]    1    4    7
## [2,]    2    5    8
## [3,]    3    6    9
write('Printing Lower Triangular Matrix L:', stdout())
## Printing Lower Triangular Matrix L:
b$L ## [,1] [,2] [,3] ## [1,] 1 0 0 ## [2,] 2 1 0 ## [3,] 3 2 1 write('Printing Upper Triangular Matrix U:', stdout()) ## Printing Upper Triangular Matrix U: b$U
##      [,1] [,2] [,3]
## [1,]    1    4    7
## [2,]    0   -3   -6
## [3,]    0    0    0