DATA605_Homework2

library(tidyverse)

Problem Set 1

Show that \(A^{T}A \neq AA^{T}\) in general. (Proof and demonstration.)
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).

Solution (1)

Proof to show that \(A^{T}A \neq AA^{T}\)

Proof

Suppose a matrix \(A\) is an \(m \times n\) matrix and a matrix \(B\) is an \(n \times p\) matrix. Let vectors \(A_{1}, A_{2}, A_{3},...,A_{n}\) denote the columns of \(A\) and let the vectors \(B_{1}, B_{2}, B_{3},...,B_{p}\) denote the columns of \(B\).

Then for \(1\leq i\leq m, 1\leq j\leq p\), the individual entries of \(AB\) are:

\[[AB]_{ij} = [AB_{j}]_{i}\] \[= [ [B_{j}]_{1}A_{1} + [B_{j}]_{2}A_{2} + \cdots + [B_{j}]_{n}A_{n} ]_{i}\] \[= [ [B_{j}]_{1}A_{1}]_{i} + [[B_{j}]_{2}A_{2}]_{i} + \cdots + [[B_{j}]_{n}A_{n} ]_{i}\] \[= [B_{j}]_{1}[A_{1}]_{i} + [B_{j}]_{2}[A_{2}]_{i} + \cdots + [B_{j}]_{n}[A_{n}]_{i}\] \[= [B_{1j}][A]_{i1} + [B_{2j}][A]_{i2} + \cdots + [B_{nj}][A]_{in} \] \[= [A_{i1}][B]_{1j} + [A_{i2}][B]_{2j} + \cdots + [A_{in}][B]_{nj}\] \[= \sum_{k=1}^{n} [A]_{ik}[B]_{kj}\]

Base on the proof above, suppose the matrix \(A\) is an \(m \times n\) matrix, which implies that \(A^{T}\) is an \(n \times m\) matrix. Then for \(1\leq i\leq m, 1\leq j\leq m\), the individual entries of \(AA^{T}\) are given by \[[AA^{T}]_{ij} = [A]_{i1}[A^{T}]_{1j} + [A]_{i2}[A^{T}]_{2j} + [A]_{i3}[A^{T}]_{3j} + \cdots + [A]_{in}[A^{T}]_{nj}\] \[= \sum_{k=1}^{n} [A]_{ik}[A^{T}]_{kj}\]

And for \(1\leq i\leq n, 1\leq j\leq n\), the individual entries of \(A^{T}A\) are given by \[[A^{T}A]_{ij} = [A^{T}]_{i1}[A]_{1j} + [A^{T}]_{i2}[A]_{2j} + [A^{T}]_{i3}[A]_{3j} + \cdots + [A^{T}]_{im}[A]_{mj}\] \[= \sum_{k=1}^{m} [A^{T}]_{ik}[A]_{kj}\] , where \(AA^{T}\) is an \(m \times m\) matrix and \(A^{T}A\) is an \(n \times n\) matrix.

Therefore, \(A^{T}A \neq AA^{T}\) in general.

Demostration.

\[ { A }^{ T }A \neq A{ A }^{ T } \]

Suppose we have matrix A and its transpose

Let \(A=\begin{bmatrix} 2 & -1 \\ 3 & 2 \end{bmatrix}\) and \(\\{ A }^{ T }=\begin{bmatrix} 2 & 3 \\ -1 & 2 \end{bmatrix}\)

calculate \(A^{T}A\) and \(AA^{T}\).

Using matrix multiplication, we evaluate the matrix above

\[ { A }^{ T }A= \begin{bmatrix} 2 & 3 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\\ { A }^{ T }A= \begin{bmatrix} 4+9 & -2+3 \\ -2+3 & 1+1 \end{bmatrix}\\ { A }^{ T }A= \begin{bmatrix} 13 & 1 \\ 1 & 2 \end{bmatrix} \]

\[ A{ A }^{ T }= \begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ -1 & 1 \end{bmatrix}\\ A{ A }^{ T }= \begin{bmatrix} 4+1 & 6-1 \\ 6-1 & 9+1 \end{bmatrix}\\ A{ A }^{ T }= \begin{bmatrix} 5 & 5 \\ 5 & 10 \end{bmatrix} \]

\({ A }^{ T }A= \begin{bmatrix} 13 & 1 \\ 1 & 2 \end{bmatrix}\) and \(A{ A }^{ T }= \begin{bmatrix} 5 & 5 \\ 5 & 10 \end{bmatrix}\)

Hence, we conclude that: \({ A }^{ T }A \neq A{ A }^{ T }\)

\[ { A }^{ T }A\neq A{ A }^{ T } \]

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

Solution

Based on the proof in Part(1), we have two equations: \[[A^{T}A]_{ij} = \sum_{k=1}^{m} [A^{T}]_{ik}[A]_{kj}\] \[[AA^{T}]_{ij} = \sum_{k=1}^{n} [A]_{ik}[A^{T}]_{kj}\]

In order to have \(A^{T}A = AA^{T}\), we need \(m=n\) and \(A = A^{T}\), which implies \(A\) has to be a symmetric matrix.

Problem Set 2: Matrix Factorization

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

Solution

We then can build a factorization function to decompose a square matrix into an L and U matrix.

factorize <- function(mtx,n){
  
  # Create empty matrix for lower and upper triangular matrix 
  lower <- matrix(0, nrow=n, ncol=n)
  upper <- matrix(0, nrow=n, ncol=n)
  
  # Decomposing matrix into upper and lower triangular matrix using loop
  for (i in 1:n){
    
    # Upper triangular
    for (k in i:n){
      
      # Summation of L[i, j] * U[j, k]
      sum <- 0
      for (j in 1:i){
        sum <- sum + (lower[i,j] * upper[j,k])
      }
      
      # Evaluating U[i, k] 
      upper[i,k] <- mtx[i,k] - sum
      
    }
  
    # Lower Triangular
    for (k in i:n){
      
      if (i==k){
        lower[i,i] <- 1 # Diagonal as 1
      } else{
        
            # Summation of L[k, j] * U[j, i]
            sum <- 0
            for (j in 1:i){
              sum <- sum + (lower[k,j] * upper[j,i])
            }
            
            # Evaluating L[k, i]
            lower[k,i] = (mtx[k,i] - sum) / upper[i,i]
      }
    }
  }
  
  list <- list("U"=upper, "L"=lower)
  return(list)

}

To test the Function using a 3X3 square matrix

# Using a sample 3x3 square matrix to test the function
mtx <- matrix(c(1,1,2,2,1,0,3,4,3), byrow=T, nrow=3)

factorize(mtx,3)

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

To check if LU = mtx

# Checking if LU = mtx
factorize(mtx,3)$L %*% factorize(mtx,3)$U

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

Hence, we say the function is valid and correct