Problem Set 1

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

Proof by contradiction: Let: \[ A = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \\ A^T = \begin{bmatrix} a & c \\ b & d \\ \end{bmatrix} \]

Therefore:

\[ A^TA = \begin{bmatrix} a^2+b^2 & ac + bd \\ ac +bd & c^2 + d^2 \\ \end{bmatrix} \\ AA^T = \begin{bmatrix} a^2+c^2 & ab + cd \\ ab - bd & b^2 + d^2 \\ \end{bmatrix} \]

Thus, we can see that \(\forall\quad b \neq c\) the product of \(A^TA \neq AA^T\). Therefor in general, unless the transposes are equal, they will not produce the same result.

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

identical(t(A) %*% A, A %*% t(A))
## [1] FALSE

So we can see they are not identical, however…

A <- matrix(c(1,3,3,4), ncol = 2)
identical(t(A) %*% A, A %*% t(A))
## [1] TRUE

So when the matrix can be inverted, it is true.

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).

See extended answer to 1. In general if the matrix has a transpose equal to the original matrix it will be have this characteristic.

Problem Set 2

Matrix factorization is a very important problem. There are supercomputers built just to do matrix factorization. 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.

Unfortunately the solution we used for last weeks assignment is a bit complex to use for this case. Instead we will you a more basic function that only worries about creating an upper triangular matrix and then take the negative of the row multiplier and insert it into the correct position. Special thanks to this website for giving me an easier way to itterate over all rows.

set.seed(605)
n <- 5
A <- matrix(sample.int(10, size = n^2, replace = TRUE), ncol = n)
A
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    3    9    7    8    1
## [2,]    3    6    2    4    2
## [3,]    1   10   10    3    4
## [4,]    2   10    5    7   10
## [5,]    2    8   10    1    9
matrixLU <- function(A){
  U = A # to keep consistant formatting.
  L = diag(x = 1, ncol = ncol(A), nrow = nrow(A)) # Square diagonal to populate cells.
  
  # For loops to loop over elements in L and U
  for (i in 1:(nrow(U) - 1)){
    for (j in (i + 1):nrow(U)){
      if (U[i, i] != 0){
        multiplier = U[j, i] / U[i, i]
        L[j, i] = multiplier
        U[j, ] = U[j, ] - multiplier * U[i, ]
      }
    }
  }
  return(list('L' = L, 'U' = U))
}

X <- matrixLU(A)
X$L
##           [,1]       [,2]      [,3]      [,4] [,5]
## [1,] 1.0000000  0.0000000  0.000000  0.000000    0
## [2,] 1.0000000  1.0000000  0.000000  0.000000    0
## [3,] 0.3333333 -2.3333333  1.000000  0.000000    0
## [4,] 0.6666667 -1.3333333  1.583333  1.000000    0
## [5,] 0.6666667 -0.6666667 -0.500000 -1.086614    1
X$U
##      [,1] [,2] [,3]     [,4]      [,5]
## [1,]    3    9    7  8.00000  1.000000
## [2,]    0   -3   -5 -4.00000  1.000000
## [3,]    0    0   -4 -9.00000  6.000000
## [4,]    0    0    0 10.58333  1.166667
## [5,]    0    0    0  0.00000 13.267717
X$L %*% X$U
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    3    9    7    8    1
## [2,]    3    6    2    4    2
## [3,]    1   10   10    3    4
## [4,]    2   10    5    7   10
## [5,]    2    8   10    1    9
B <-  matrix(c(1:16), ncol = 4)
X1 <- matrixLU(B)
X1$L
##      [,1] [,2] [,3] [,4]
## [1,]    1    0    0    0
## [2,]    2    1    0    0
## [3,]    3    2    1    0
## [4,]    4    3    0    1
X1$U
##      [,1] [,2] [,3] [,4]
## [1,]    1    5    9   13
## [2,]    0   -4   -8  -12
## [3,]    0    0    0    0
## [4,]    0    0    0    0
all.equal(X1$L %*% X1$U, B)
## [1] TRUE