Problem Set 1

Part 1

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

Proof by contradiction:

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