Data 605-Homework2

Problem 1

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

Indirect Proof:

• Consider \(A^T A = A A^T\)
• If A = \(\begin{bmatrix} 2 & 3 \\2 & 4\end{bmatrix}\) then \(A^T\) = \(\begin{bmatrix} 2 & 2 \\3 & 4\end{bmatrix}\)
• \(A^T A = \begin{bmatrix} 2 & 3 \\2 & 4\end{bmatrix}\begin{bmatrix} 2 & 2 \\3 & 4\end{bmatrix} = \begin{bmatrix} 13 & 16 \\16 & 20\end{bmatrix}\)
• but \(A A^T = \begin{bmatrix} 2 & 2 \\3 & 4\end{bmatrix}\begin{bmatrix} 2 & 3 \\2 & 4\end{bmatrix} = \begin{bmatrix} 8 & 14 \\14 & 25\end{bmatrix}\)
• In general \(A^T A \neq AA^T\)

A = matrix(c(2,2,3,4), nrow=2, ncol=2)
A

##      [,1] [,2]
## [1,]    2    3
## [2,]    2    4

AT <- t(A)
AT

##      [,1] [,2]
## [1,]    2    2
## [2,]    3    4

# Multiplying A by its transpose we get 2x2
A %*% AT

##      [,1] [,2]
## [1,]   13   16
## [2,]   16   20

# Multiplying transposed A by A we get 2x2
AT %*% A

##      [,1] [,2]
## [1,]    8   14
## [2,]   14   25

The results shows that \(A^T A ≠ AA^T\).

Problem 1 Part 2

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

This could be True for symmetric matrices. A symmetric matrix can be derived by multiplying any \(A\) by \(A^T\) or \(A^T\) by either \(A\) to get \(S\). Transposing a matrix switches columns into rows or simply flips it along the diagonal. If a matrix is symmetrical along the diagonal, \(A^T\) = \(A\) and the condition holds.

# For a given Matrix A
A <- matrix(c(1,2,1,0,1,0,0,2,3), nrow=3, byrow=TRUE)
A

##      [,1] [,2] [,3]
## [1,]    1    2    1
## [2,]    0    1    0
## [3,]    0    2    3

t(A) # The transpose is same

##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    2    1    2
## [3,]    1    0    3

A == t(A)

##       [,1]  [,2]  [,3]
## [1,]  TRUE FALSE FALSE
## [2,] FALSE  TRUE FALSE
## [3,] FALSE FALSE  TRUE

The condition holds if a matrix is symmetrical along the diagonal.

Problem 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 you prefer. 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.

Function to Solve A = LU

This code was obtained from the algorithm presented by James Sousa online

factorizeLU <- function(A) {
  # Check that A is square
  if (dim(A)[1]!=dim(A)[2]) {
    return(NA)
  }
  
  U <- A
  n <- dim(A)[1]
  L <- diag(n)
  
  # If dimension is 1, then U=A and L=[1]
  if (n==1) {
    return(list(L,U))
  }
  
  # Loop through the lower triangle (by rows and columns)
  # Determine multiplier for each position and add it to L
  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,U))
}

Testing the code on a 3 x 3 matrix

A <- matrix(c(1,2,-2,3,3,2,1,2,4), nrow=3, byrow=TRUE)
LU <- factorizeLU(A)
L<-LU[[1]]  
U<-LU[[2]]

A

##      [,1] [,2] [,3]
## [1,]    1    2   -2
## [2,]    3    3    2
## [3,]    1    2    4

Proof

A == L %*% U

##      [,1] [,2] [,3]
## [1,] TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE