IS 605 FUNDAMENTALS OF COMPUTATIONAL MATHEMATICS - 2015
For a n x m matrix A, \[ A^T \] is a m x n matrix. \[ A^TA \] is m x m matrix. \[ AA^T \] is a n x n matrix.
If \[ n \neq m \], the size of \[ A^TA \] and \[ AA^T \] are different, then we know \[ A^TA \neq AA^T \]
Even if n = m and \[ A^TA \] and \[ AA^T \] are the same size square matrices, \[ A^TA \] and \[ AA^T \] are not equal at most of the time.
According to Theorem MMT Matrix Multiplication and Transposes, Suppose A is an m x n matrix and B is an n x m matrix.
As per the properties of transpose for some matrix A. Suppose we also have some matrix B, not equal to A, and some real constant k: \[ (A^T)^T = A \] \[ (A+B)^T = A^T + B^T \] \[ (kA)^T = kA^T \] \[ (AB)^T = B^TA^T \] \[ (A^TA)^T = A^T(A^T)^T = A^TA \]
So \[ A^TA \] is the transpose of itself.
Assuming, \[ A^TA = AA^T \], replacing A with \[ A^TA \] to identify if the rule holds good \[ (A^TA)^T = (AA^T)^T = (A^T)^TA^T \] As can be seen from above, since \[ (A^TA)A^T = (A^T)^TA^T \] is against Theorem MMT, so the assumption is not right and should be \[ A^TA \neq AA^T \]
Let’s prove it mathematically with A and it’s transpose be defined as follows:
\[ A = \left[\begin{array}{rrr}a & b\\c & d\end{array}\right] \] \[ A^T = \left[\begin{array}{rrr}a & c\\b & d\end{array}\right] \] \[ AA^T = \left[\begin{array}{rrr}a & b\\c & d\end{array}\right]\left[\begin{array}{rrr}a & c\\b & d\end{array}\right] = \left[\begin{array}{rrr}(a*a)+(b*b) & (a*c)+(b*d)\\(c*a)+(d*b) & (c*c)+(d*d)\end{array}\right] = \left[\begin{array}{rrr}(a^2+b^2) & (ac+bd)\\(ac+bd) & (c^2+d^2)\end{array}\right] \] \[ A^TA = \left[\begin{array}{rrr}a & c\\b & d\end{array}\right]\left[\begin{array}{rrr}a & b\\c & d\end{array}\right] = \left[\begin{array}{rrr}(a*a)+(c*c) & (a*b)+(c*d)\\(b*a)+(d*c) & (b*b)+(d*d)\end{array}\right] = \left[\begin{array}{rrr}(a^2+c^2) & (ab+cd)\\(ab+cd) & (b^2+d^2)\end{array}\right] \] Again, we can see that since \[ \left[\begin{array}{rrr}(a^2+b^2) & (ac+bd)\\(ac+bd) & (c^2+d^2)\end{array}\right] \neq \left[\begin{array}{rrr}(a^2+c^2) & (ab+cd)\\(ab+cd) & (b^2+d^2)\end{array}\right] \], thus \[ AA^T \neq A^TA \]
For example, \[ A = \left[\begin{array}{rrr}1 & 2\\3 & 4\end{array}\right] \] \[ A^T = \left[\begin{array}{rrr}1 & 3\\2 & 4\end{array}\right] \] \[ AA^T = \left[\begin{array}{rrr}(1*1)+(2*2) & (1*3)+(2*4)\\(3*1)+(4*2) & (3*3)+(4*4)\end{array}\right] = \left[\begin{array}{rrr}5 & 11\\11 & 25\end{array}\right] \] \[ A^TA = \left[\begin{array}{rrr}(1*1)+(3*3) & (1*2)+(3*4)\\(2*1)+(4*3) & (2*2)+(4*4)\end{array}\right] = \left[\begin{array}{rrr}10 & 14\\14 & 20\end{array}\right] \]
A = matrix(c(1,2,3,4), nrow=2, ncol=2, byrow=TRUE)
paste0("A=")## [1] "A="A## [,1] [,2]
## [1,] 1 2
## [2,] 3 4paste0("t(A)=")## [1] "t(A)="t(A)## [,1] [,2]
## [1,] 1 3
## [2,] 2 4AtA <- A%*%t(A)
paste0("A*t(A)=")## [1] "A*t(A)="AtA## [,1] [,2]
## [1,] 5 11
## [2,] 11 25tAA <- t(A)%*%A
paste0("t(A)*A=")## [1] "t(A)*A="tAA## [,1] [,2]
## [1,] 10 14
## [2,] 14 20paste0("Is A*t(A) same as t(A)*A=",identical(AtA,tAA))## [1] "Is A*t(A) same as t(A)*A=FALSE"Thus, \[ (A^TA)^T=(A^T)^TA^T \] is against Theorem MMT, so the assumption \[ A^TA = AA^T \] is not right, which means \[ A^TA \neq AA^T \] in general.
(Hint: The Identity matrix I is an example of such a matrix).
Please typeset your response using LaTeX mode in RStudio. If you do it in paper, please either scan or take a picture of the work and submit it. Please ensure that your image is legible and that your submissions are named using your rst initial, last name, assignment and problem set within the assignment. E.g. LFulton_Assignment2_PS1.png
For example, \[ A = \left[\begin{array}{rrr}1 & 2\\2 & 1\end{array}\right] \] \[ A^T = \left[\begin{array}{rrr}1 & 2\\2 & 1\end{array}\right] \]
A = matrix(c(1,2,2,1), nrow=2, ncol=2, byrow=TRUE)
paste0("A=")## [1] "A="A## [,1] [,2]
## [1,] 1 2
## [2,] 2 1paste0("t(A)=")## [1] "t(A)="t(A)## [,1] [,2]
## [1,] 1 2
## [2,] 2 1AtA <- A%*%t(A)
paste0("A*t(A)=")## [1] "A*t(A)="AtA## [,1] [,2]
## [1,] 5 4
## [2,] 4 5tAA <- t(A)%*%A
paste0("t(A)*A=")## [1] "t(A)*A="tAA## [,1] [,2]
## [1,] 5 4
## [2,] 4 5paste0("Is A*t(A) same as t(A)*A=",identical(AtA,tAA))## [1] "Is A*t(A) same as t(A)*A=TRUE"Hence, we can confirm that when \[ A = A^T \] it would result in \[ AA^T = A^TA \], which includes the Identity Matrix I since Identity Matrix is a sub-set/special example of A where \[ A = \left[\begin{array}{rrr}a & x\\x & a\end{array}\right] \] and \[ I = \left[\begin{array}{rrr}1 & 0\\0 & 1\end{array}\right] \]
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. 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.
factorizeLU <- function(A) {
# Check that A is square
if (dim(A)[1]!=dim(A)[2]) {
return(NA)
}
U <- A
n <- dim(A)[1]
L <- diag(n)
# If dimension is 1, then U=A and L=[1]
if (n==1) {
return(list(L,U))
}
# Loop through the lower triangle (by rows and columns)
# Determine multiplier for each position and add it to L
for(i in 2:n) {
for(j in 1:(i-1)) {
multiplier <- -U[i,j] / U[j,j]
U[i, ] <- multiplier * U[j, ] + U[i, ]
L[i,j] <- -multiplier
}
}
return(list(L,U))
}
#Test with 3x3 matrix
X <- matrix(c(1,4,-3,-2,8,5,3,4,7), nrow=3, byrow=TRUE)
print("X=")## [1] "X="X## [,1] [,2] [,3]
## [1,] 1 4 -3
## [2,] -2 8 5
## [3,] 3 4 7LU <- factorizeLU(X)
L<-LU[[1]]
print("L=")## [1] "L="L## [,1] [,2] [,3]
## [1,] 1 0.0 0
## [2,] -2 1.0 0
## [3,] 3 -0.5 1U<-LU[[2]]
print("U=")## [1] "U="U## [,1] [,2] [,3]
## [1,] 1 4 -3.0
## [2,] 0 16 -1.0
## [3,] 0 0 15.5X == L %*% U## [,1] [,2] [,3]
## [1,] TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE
## [3,] TRUE TRUE TRUEpaste0("Is X same as LU=",identical(X,L%*%U))## [1] "Is X same as LU=TRUE"#Test with 2x2 matrix
Y <- matrix(c(2,1,6,8), nrow=2, byrow=TRUE)
print("Y=")## [1] "Y="Y## [,1] [,2]
## [1,] 2 1
## [2,] 6 8LU <- factorizeLU(Y)
L<-LU[[1]]
print("L=")## [1] "L="L## [,1] [,2]
## [1,] 1 0
## [2,] 3 1U<-LU[[2]]
print("U=")## [1] "U="U## [,1] [,2]
## [1,] 2 1
## [2,] 0 5Y == L %*% U## [,1] [,2]
## [1,] TRUE TRUE
## [2,] TRUE TRUEpaste0("Is Y same as LU=",identical(Y,L%*%U))## [1] "Is Y same as LU=TRUE"