Assignment #2
Sie Siong Wong
9/2/2020
Problem Set 1
- Show that \({ A }^{ T }A\neq A{ A }^{ T }\) in general. (Proof and demonstration.)
- For a special type of square matrix A, we get AT A = AAT . Under what conditions could this be true? (Hint: The Identity matrix I is an example of such a matrix).
Question 1:
Show that \({ A }^{ T }A\neq A{ A }^{ T }\) in general. (Proof and demonstration.)
Answer: The product of \({ A }^{ T }A\) is not equal to \(A{ A }^{ T }\) in general because the multiplication elements in rows and columns between \({ A }^{ T }A\) and \(A{ A }^{ T }\) are different. Therefore, their product matrix will be different.
To proof above explanation:
Let \(A\quad =\quad \begin{bmatrix} { x }_{ 1 } & { x }_{ 2 } \\ { y }_{ 1 } & { y }_{ 2 } \end{bmatrix}\)
and the transpose of matrix A will be \({ A }^{ T }\quad =\quad \begin{bmatrix} { x }_{ 1 } & { y }_{ 1 } \\ { x }_{ 2 } & { y }_{ 2 } \end{bmatrix}\)
So,
\({ A }^{ T }A\quad =\quad \begin{bmatrix} { x }_{ 1 }{ x }_{ 1 }\quad +\quad { y }_{ 1 }{ y }_{ 1 } & { x }_{ 1 }{ x }_{ 2 }\quad +{ \quad y }_{ 1 }{ y }_{ 2 } \\ { { x }_{ 2 }x }_{ 1 }\quad +\quad { y }_{ 2 }{ y }_{ 1 } & { x }_{ 2 }{ x }_{ 2 }\quad +{ \quad y }_{ 2 }{ y }_{ 2 } \end{bmatrix}\)
and
\({ AA }^{ T }\quad =\quad \begin{bmatrix} { x }_{ 1 }{ x }_{ 1 }\quad +\quad x_{ 2 }{ x }_{ 2 } & { x }_{ 1 }{ y }_{ 1 }\quad +\quad x_{ 2 }{ y }_{ 2 } \\ { { y }_{ 1 }x }_{ 1 }\quad +\quad { y }_{ 2 }x_{ 2 } & { y }_{ 1 }{ y }_{ 1 }\quad +{ \quad y }_{ 2 }{ y }_{ 2 } \end{bmatrix}\)
You can see that the product of the first element in \({ A }^{ T }A\) and \(A{ A }^{ T }\) are not equal, \({ x }_{ 1 }{ x }_{ 1 }\ +\ { y }_{ 1 }{ y }_{ 1 } \neq { x }_{ 1 }{ x }_{ 1 }\ +\ x_{ 2 }{ x }_{ 2 }\)
The above proof is for the 2x2 square matrix. This happens the same even for non-square matrices. For instance, the dimension of matrix A is 3 x 2 and the dimension of transpose of matrix A is 2 x 3. The product of \(A{ A }^{ T }\) which dimension is 3 x 3 while the dimension of the product of \({ A }^{ T }A\) is 2 x 2. It’s clear that \({ A }^{ T }A\neq A{ A }^{ T }\) because the dimension of matrix product for both sides are not the same.
Example of a square matrix:
From the below demonstration, we can see that the product of \(A{ A }^{ T }\) and \({ A }^{ T }A\) are not the equal.
# Create a 3x3 square matrix
mtrx_a <- matrix(c(1,1,3,2,-1,5,-1,-2,4), byrow=T, nrow=3, ncol=3)
mtrx_a## [,1] [,2] [,3]
## [1,] 1 1 3
## [2,] 2 -1 5
## [3,] -1 -2 4# Transpose of matrix A
mtrx_a_trans <- t(mtrx_a)
mtrx_a_trans## [,1] [,2] [,3]
## [1,] 1 2 -1
## [2,] 1 -1 -2
## [3,] 3 5 4# Product of matrix A with transpose of matrix A
mtrx_aat <- mtrx_a %*% mtrx_a_trans
mtrx_aat## [,1] [,2] [,3]
## [1,] 11 16 9
## [2,] 16 30 20
## [3,] 9 20 21# Product of transpose of matrix A with matrix A
mtrx_ata <- mtrx_a_trans %*% mtrx_a
mtrx_ata## [,1] [,2] [,3]
## [1,] 6 1 9
## [2,] 1 6 -10
## [3,] 9 -10 50# Checking if AAT not equal to ATA
(mtrx_aat == mtrx_ata)## [,1] [,2] [,3]
## [1,] FALSE FALSE TRUE
## [2,] FALSE FALSE FALSE
## [3,] TRUE FALSE FALSEExample of a non-square matrix:
From the below demonstration, we can see that the product of \(A{ A }^{ T }\) and \({ A }^{ T }A\) are not the equal.
# Create a 3x3 square matrix
mtrx_a2 <- matrix(c(1,2,2,6,1,0,1,3,1,0,1,1), byrow=T, nrow=3, ncol=4)
mtrx_a2## [,1] [,2] [,3] [,4]
## [1,] 1 2 2 6
## [2,] 1 0 1 3
## [3,] 1 0 1 1# Transpose of matrix A
mtrx_a2_trans <- t(mtrx_a2)
mtrx_a2_trans## [,1] [,2] [,3]
## [1,] 1 1 1
## [2,] 2 0 0
## [3,] 2 1 1
## [4,] 6 3 1# Product of matrix A with transpose of matrix A
mtrx_aat2 <- mtrx_a2 %*% mtrx_a2_trans
mtrx_aat2## [,1] [,2] [,3]
## [1,] 45 21 9
## [2,] 21 11 5
## [3,] 9 5 3# Product of transpose of matrix A with matrix A
mtrx_ata2 <- mtrx_a2_trans %*% mtrx_a2
mtrx_ata2## [,1] [,2] [,3] [,4]
## [1,] 3 2 4 10
## [2,] 2 4 4 12
## [3,] 4 4 6 16
## [4,] 10 12 16 46# Checking if AAT not equal to ATA by (mtrx_aat2 == mtrx_ata2) will be getting the non-conformable arrays error as the dimension of matrix at both sides of that equation are not the same.Question 2:
For a special type of square matrix A, we get \({ A }^{ T }A=A{ A }^{ T }\) . Under what conditions could this be true? (Hint: The Identity matrix I is an example of such a matrix).
Answer: \({ A }^{ T }A=A{ A }^{ T }\) could be true when \({ A }^{ T }\) is inverse of A and the product result of either \({ A }^{ T }A\) or \(A{ A }^{ T }\) will be equal to an identity matrix. That is if \({ A }^{ -1 }={ A }^{ T }\) then \({ A }^{ T }A=A{ A }^{ T }=I\). This means that each column vector has length one and is perpendicular to all the other column vectors. That means it is an orthonormal matrix.
To prove,
\({ A }^{ T }A=I\\ { AA }^{ T }A=AI\\ { AA }^{ T }A{ A }^{ -1 }=AI{ A }^{ -1 }\\\)
Multiplying a matrix by the identity matrix doesn’t change anything and multiplying a matrix with its inverse matrix equal to identity matrix. So,
\({ AA }^{ T }I=A{ A }^{ -1 }\\ A{ A }^{ T }=I\)
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 fights 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. Please submit your response in an R Markdown document using our class naming convention, E.g. LFulton_Assignment2_PS2.png
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. If you doing the entire assignment in R, then please submit only one markdown document for both the problems.
Answer: Function below to decompose a square matrix into lower and upper triangular matrix.
Function
Applying the Doolittle’s method to build a function to factor a square matrix into an LU decomposition. Refer to the algorithms from https://www.geeksforgeeks.org/doolittle-algorithm-lu-decomposition/.
These equations can be summarized into \({ L }_{ i,k }\) and \({ U }_{ i,k }\) as below.
We then can build a factorization function to decompose a square matrix into an L and U based on these equations.
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)
}Testing
Testing with 3x3 Square Matrix
# 3x3 square matrix for testing the function
mtx <- matrix(c(2,-1,-2,-4,6,3,-4,-2,8), byrow=T, nrow=3, ncol=3)
factorize(mtx,3)## $U
## [,1] [,2] [,3]
## [1,] 2 -1 -2
## [2,] 0 4 -1
## [3,] 0 0 3
##
## $L
## [,1] [,2] [,3]
## [1,] 1 0 0
## [2,] -2 1 0
## [3,] -2 -1 1# Checking if LU = mtx
(factorize(mtx,3)$L %*% factorize(mtx,3)$U == mtx)## [,1] [,2] [,3]
## [1,] TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE
## [3,] TRUE TRUE TRUETesting with 4x4 Square Matrix
# 4x4 square matrix for testing the function
mtx <- matrix(c(1,-2,-2,-3,3,-9,0,-9,-1,2,4,7,-3,-6,26,2), byrow=T, nrow=4, ncol=4)
factorize(mtx,4)## $U
## [,1] [,2] [,3] [,4]
## [1,] 1 -2 -2 -3
## [2,] 0 -3 6 0
## [3,] 0 0 2 4
## [4,] 0 0 0 1
##
## $L
## [,1] [,2] [,3] [,4]
## [1,] 1 0 0 0
## [2,] 3 1 0 0
## [3,] -1 0 1 0
## [4,] -3 4 -2 1# Checking if LU = mtx
(factorize(mtx,4)$L %*% factorize(mtx,4)$U == mtx)## [,1] [,2] [,3] [,4]
## [1,] TRUE TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE TRUE
## [4,] TRUE TRUE TRUE TRUETesting with 5x5 Square Matrix
# 5x5 square matrix for testing the function
mtx <- matrix(
c(4,1,2,-3,5,-3,3,-1,4,-2,-1,2,5,1,3,5,4,3,-1,2,1,-2,3,-4,5,-16,20,-4,-10,3),
byrow=T,
nrow=5,
ncol=5)
factorize(mtx,5)## $U
## [,1] [,2] [,3] [,4] [,5]
## [1,] 4 1.00 2.0 -3.000000 5.000000
## [2,] 0 3.75 0.5 1.750000 1.750000
## [3,] 0 0.00 5.2 -0.800000 3.200000
## [4,] 0 0.00 0.0 1.487179 -5.615385
## [5,] 0 0.00 0.0 0.000000 -3.603448
##
## $L
## [,1] [,2] [,3] [,4] [,5]
## [1,] 1.00 0.0000000 0.00000000 0.000000 0
## [2,] -0.75 1.0000000 0.00000000 0.000000 0
## [3,] -0.25 0.6000000 1.00000000 0.000000 0
## [4,] 1.25 0.7333333 0.02564103 1.000000 0
## [5,] 0.25 -0.6000000 0.53846154 -1.189655 1# Checking if LU = mtx
(factorize(mtx,5)$L %*% factorize(mtx,5)$U == mtx)## [,1] [,2] [,3] [,4] [,5]
## [1,] TRUE TRUE TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE TRUE TRUE
## [4,] TRUE TRUE TRUE TRUE TRUE
## [5,] TRUE TRUE TRUE TRUE TRUE