Problem Set 1

  1. Show that \(A^{T}A \neq AA^{T}\) in general.

Matrix multiplication is not commutative. The order in which we multiply matrices matters, and for this reason \(A^{T}A \neq AA^{T}\) generally, since \(A^{T} \neq A\).

\[A = \begin{bmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & & a_{2n}\\ \vdots & & \ddots & \vdots\\ a_{m1} & \cdots & & a_{mn} \end{bmatrix} \enspace A^{T} = \begin{bmatrix}a_{11} & a_{21} & \cdots & a_{m1}\\ a_{12} & a_{22} & & a_{m2}\\ \vdots & & \ddots & \vdots\\ a_{1n} & \cdots & & a_{mn} \end{bmatrix}\]

We can see from here the result of \(A^{T}A\) would be an nxn matrix while the result of \(AA^{T}\) would be an mxm matrix. If \(n \neq m\) then these matrices can obviously not be equal since they have different dimensions.

For example, suppose we have \(A\) and \(A^{T}\) as follows:

\[A = \begin{bmatrix}a & b & c\\ d & e & f \end{bmatrix} \enspace A^{T} = \begin{bmatrix}a & d\\ b & e\\ c & f \end{bmatrix}\]

Since \(A\) is a 2x3 matrix, and \(A^{T}\) is a 3x2 matrix, the result of \(A^{T}A\) will be a 3x3 matrix as follows:

\[A^{T}A = \begin{bmatrix}a & b & c\\ d & e & f \end{bmatrix} \begin{bmatrix}a & d\\ b & e\\ c & f\\ \end{bmatrix} = \begin{bmatrix}a^{2}+d^{2} & ab+de & ac+df\\ ba+ed & b^{2}+e^{2} & bc+ef\\ ca+fd & cb+fe & c^{2}+f^{2} \end{bmatrix}\]

The result of \(AA^{T}\) will likewise be a 2x2 matrix as follows:

\[AA^{T} = \begin{bmatrix}a & d\\ b & e\\ c & f\\ \end{bmatrix} \begin{bmatrix}a & b & c\\ d & e & f \end{bmatrix}= \begin{bmatrix}a^{2}+b^{2}+c^{2} & ab+be+cf\\ da+eb+fc & d^{2}+e^{2}+f^{2}\\ \end{bmatrix}\]

We see here that \(A^{T}A \neq AA^{T}\):

\[\begin{bmatrix}a^{2}+d^{2} & ab+de & ac+df\\ ba+ed & b^{2}+e^{2} & bc+ef\\ ca+fd & cb+fe & c^{2}+f^{2} \end{bmatrix} \neq \begin{bmatrix}a^{2}+b^{2}+c^{2} & ab+be+cf\\ da+eb+fc & d^{2}+e^{2}+f^{2}\\ \end{bmatrix}\]

So, generally, \(A^{T}A \neq AA^{T}\) as \(A^{T} \neq A\).

  1. For a special type of square matrix 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).

\(A^{T}A = AA^{T}\) for symmetric square matrices such that \(A^{T} = A\). This means that the rows of \(A\) are the same as the columns of \(A\), and as such, the transpose of matrix \(A\) would remain \(A\) itself. This would include diagonal square matrices, such as the identity matrix, as the transpose of any such matrix would be the same as the original matrix.

\[\begin{bmatrix} a & b & c\\ b & d & e\\ c & e & f \end{bmatrix}^{T} = \begin{bmatrix} a & b & c\\ b & d & e\\ c & e & f \end{bmatrix}\]

Problem Set 2

Write an R function to factorize a square matrix A into LU or LDU, whichever you prefer.

Here I figured out how to perform LU factorization on matrix A:

A <- matrix(c(1,2,3,1,1,1,2,0,1),nrow=3)

U = A
L = diag(nrow(A))
  
for (i in 1:(nrow(A)-1)) {
  for (j in (i+1):nrow(A)) {
    L[j,i] = U[j,i]/U[i,i]
    U[j,] = U[j,] - L[j,i]*U[i,]
  }
}

L
##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    2    1    0
## [3,]    3    2    1
U
##      [,1] [,2] [,3]
## [1,]    1    1    2
## [2,]    0   -1   -4
## [3,]    0    0    3

The Completed Function

luFactorize <- function(A) {
  U <-  A
  L <-  diag(nrow(A))
    
  for (i in 1:(nrow(A)-1)) {
    for (j in (i+1):nrow(A)) {
      L[j,i] = U[j,i]/U[i,i]
      U[j,] = U[j,] - L[j,i]*U[i,]
    }
  }
  
  LU <- list("L" = L, "U" = U)
  
  return(LU)
}

Testing the function to make sure it works properly:

test3x3 <- luFactorize(matrix(c(1,2,3,1,1,1,2,0,1), nrow=3))
test3x3$L %*% test3x3$U == matrix(c(1,2,3,1,1,1,2,0,1), nrow=3)
##      [,1] [,2] [,3]
## [1,] TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE
test4x4 <- luFactorize(matrix(c(1,2,3,1,1,1,2,0,1,4,6,2,0,5,1,3), nrow=4))
test4x4$L %*% test4x4$U == matrix(c(1,2,3,1,1,1,2,0,1,4,6,2,0,5,1,3), nrow=4)
##      [,1] [,2] [,3] [,4]
## [1,] TRUE TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE TRUE
## [4,] TRUE TRUE TRUE TRUE