Problem Set 1

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

Proof

Let A = \((m \times n)\) = \[ {\begin{bmatrix} x_{1} \; x_{2} \; x_{3} \\ y_{1} \; y_{2} \; y_{3} \\ z_{1} \; z_{2} \; z_{3} \end{bmatrix}} \] \(A^T = (n \times m)\) = \[ {\begin{bmatrix} x_{1} \; y_{1} \; z_{1} \\ x_{2} \; y_{2} \; z_{2} \\ x_{3} \; y_{3} \; z_{3} \end{bmatrix}} \] \(A^TA\) =

\[ {\begin{bmatrix} {x_{1}}^{2} + {y_{1}}^{2} + {z_{1}}^{2} \;\;\;\;\;\;\;\;\;\;\;\;\; x_{1} x_{2} + y_{1} y_{2} + z_{1} z_{2} \;\;\;\;\;\;\; x_{1} x_{3} + y_{1} y_{3} + z_{1} z_{3} \\ x_{2} x_{1} + y_{2} y_{1} + z_{2} z_{1} \;\;\;\;\;\;\; {x_{2}}^{2} + {y_{2}}^{2} + {z_{2}}^{2} \;\;\;\;\;\;\;\;\;\;\;\; x_{2} x_{3} + y_{2} y_{3} + z_{2} z_{3} \\ x_{3} x_{1} + y_{3} y_{1} + z_{3} z_{1} \;\;\;\;\;\;\;\; x_{3} x_{2} + y_{3} y_{2} + z_{3} z_{2} \;\;\;\;\;\;\;\;\;\;\;\; {x_{3}}^{2} + {y_{3}}^{2} + {z_{3}}^{2} \\ \end{bmatrix}} \]

\(AA^T\) = \[ {\begin{bmatrix} {x_{1}}^{2} + {x_{2}}^{2} + {x_{3}}^{2} \;\;\;\;\;\;\;\;\;\;\;\; x_{1} y_{1} + x_{2} y_{2} + x_{3} y_{3} \;\;\;\;\;\;\; x_{1} z_{1} + x_{2} z_{2} + x_{3} z_{3} \\ y_{1} x_{1} + y_{2} x_{2} + y_{3} x_{3} \;\;\;\;\;\;\; {y_{1}}^{2} + {y_{2}}^{2} + {y_{3}}^{2} \;\;\;\;\;\;\;\;\;\;\;\;\;\; y_{1} z_{1} + y_{2} z_{2} + y_{3} z_{3} \\ z_{1} x_{1} + z_{2} x_{2} + z_{3} x_{3} \;\;\;\;\;\;\;\; z_{1} y_{1} + z_{2} y_{2} + z_{3} y_{3} \;\;\;\;\;\;\;\;\;\;\;\;\;\; {z_{1}}^{2} + {z_{2}}^{2} + {z_{3}}^{2} \\ \end{bmatrix}} \] This shows that \(A^TA\neq AA^T\)

Demonstration:

(A <- matrix(c(1:9), nrow=3))
##      [,1] [,2] [,3]
## [1,]    1    4    7
## [2,]    2    5    8
## [3,]    3    6    9
(AT <- t(A))
##      [,1] [,2] [,3]
## [1,]    1    2    3
## [2,]    4    5    6
## [3,]    7    8    9
(ATA <- t(A)%*%A)
##      [,1] [,2] [,3]
## [1,]   14   32   50
## [2,]   32   77  122
## [3,]   50  122  194
(AAT <- A%*%t(A))
##      [,1] [,2] [,3]
## [1,]   66   78   90
## [2,]   78   93  108
## [3,]   90  108  126

\(A^TA\neq AA^T\) in general.

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

This can happen when lower and upper triangular elements without diagonal are mirror image. Eg:

(A <- matrix(c(5,2,4,2,0,2,4,2,5), nrow = 3, byrow = T))
##      [,1] [,2] [,3]
## [1,]    5    2    4
## [2,]    2    0    2
## [3,]    4    2    5
(AT <- t(A))
##      [,1] [,2] [,3]
## [1,]    5    2    4
## [2,]    2    0    2
## [3,]    4    2    5
(ATA <- t(A)%*%A)
##      [,1] [,2] [,3]
## [1,]   45   18   44
## [2,]   18    8   18
## [3,]   44   18   45
(AAT <- A%*%t(A))
##      [,1] [,2] [,3]
## [1,]   45   18   44
## [2,]   18    8   18
## [3,]   44   18   45
ATA == AAT
##      [,1] [,2] [,3]
## [1,] TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE

Since both are same, \(A^TA= AA^T\)

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.

fun.lu <- function(A){
  if(nrow(A) != ncol(A)){
    stop("Cannot proceed with non square matrix")
  }
    else {
    n <- nrow(A)
    L <- diag(n)
    U <- A
      for (i in 1:(n - 1)) {
      for (j in (i + 1):n) {
        L[j, i] <- U[j, i] / U[i, i]
        U[j, ]  <- U[j, ] - L[j, i] * U[i, ]
      }
    }
        LU <- list("L" = L, "U" = U)
    }
}
(A <- matrix(c(1:9), nrow=3))
##      [,1] [,2] [,3]
## [1,]    1    4    7
## [2,]    2    5    8
## [3,]    3    6    9
(fun.lu(A))
## $L
##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    2    1    0
## [3,]    3    2    1
## 
## $U
##      [,1] [,2] [,3]
## [1,]    1    4    7
## [2,]    0   -3   -6
## [3,]    0    0    0