Problem Set 1

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

Proof:

Suppose \(A\) is an \(m \times n\) matrix, then \(A^T\) by the definition of a transpose matrix would be an \(n \times m\) matrix.

By the definition of matrix multiplication, multiplying \(A^T\) an \(n \times m\) matrix by \(A\) an \(m \times n\) matrix will always result in a square \(n \times n\) matrix.

Likewize, multiplying \(A\) an \(m \times n\) matrix by \(A^T\) an \(n \times m\) matrix will always result in a square \(m \times m\) matrix.

Therefore, if \(m \neq n\), the result of \(A^TA\) (a square \(n \times n\) matrix) will always be of different dimensions than \(AA^T\) (a square \(m \times m\) matrix).

Therefore, \(A^TA \neq AA^T\).

Demonstration:

\[ \text{If } A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \text{, then } A^T = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} \]

\[ A^TA = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} \times \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} = \begin{bmatrix} 17 & 22 & 27 \\ 22 & 29 & 36 \\ 27 & 36 & 45 \end{bmatrix} \]

\[ AA^T = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \times \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} = \begin{bmatrix} 14 & 32 \\ 32 & 77 \end{bmatrix} \]

\[A^TA \neq AA^T\]


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

For symmetric matrices, since \(A = A^T\), \(A^TA = AA^T\).

Example:

\[ \text{If } A \text{ equals } \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 3 & 4 & 5 \end{bmatrix} \text{, then } A^T \text{also equals } \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 3 & 4 & 5 \end{bmatrix} \]

\[ A^TA = AA^T = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 3 & 4 & 5 \end{bmatrix} \times \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 3 & 4 & 5 \end{bmatrix} = \begin{bmatrix} 14 & 20 & 26 \\ 20 & 29 & 38 \\ 26 & 38 & 50 \end{bmatrix} \]


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

A <- matrix(c(-3, 1, 2, 6, 2, -5, 9, 5, -6), nrow = 3, byrow = TRUE)

LU_factorization <- function(A) {
  
  L <- matrix(c(rep(0, nrow(A)*nrow(A))), nrow = nrow(A))
  U <- A
  
  for(j in 1:(nrow(U))) {
    
    if(j <= nrow(U)) {
      L[j:nrow(U),j] <- U[j:nrow(U),j] / U[j,j]
    }
    
    if(j < nrow(U)) {
        for(k in j:(nrow(U)-1)) {
          k <- k + 1
          # make other rows in column j zero by adding a multiple of row j 
          # (row op 3)
          U[k, ] <- U[k, ] + (U[j, ] * (-1 * U[k,j] / U[j,j])) 
      }
    }
  }
  return(list(L, U))
}

# Test the given system of equations
LU_factorization(A)
## [[1]]
##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]   -2    1    0
## [3,]   -3    2    1
## 
## [[2]]
##      [,1] [,2] [,3]
## [1,]   -3    1    2
## [2,]    0    4   -1
## [3,]    0    0    2
# Not required, but let's test a non-square matrix
# This doesn't work!!!!  
# Would need to add code to avoid division by zero and skip to the next column when calculating L
B <- matrix(c(4, -3, -1, 5, 2, -16, 12, 2, -17, -7, 8, -6, -12, 22, 10), nrow = 3, byrow = TRUE)
B
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    4   -3   -1    5    2
## [2,]  -16   12    2  -17   -7
## [3,]    8   -6  -12   22   10
b <- c(0, 0, 0)
LU_factorization(B)
## [[1]]
##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]   -4  NaN    0
## [3,]    2  NaN  NaN
## 
## [[2]]
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    4   -3   -1    5    2
## [2,]    0    0   -2    3    1
## [3,]  NaN  NaN  NaN  NaN  NaN