### Problem Set 1

#### Part 1

Show that: $A^TA \neq AA^T$

Proof:

One of the basic laws of matrices is:

$AB \neq BA$

This law shows that matrix multiplication is not commutative, therefore $A^TA \neq AA^T$

Demonstation:

Generate a random matrix A:

matrix_A = matrix(sample(1:20, 9, replace = TRUE), nrow = 3, ncol = 3)
print(matrix_A)
##      [,1] [,2] [,3]
## [1,]    5   12    4
## [2,]   13   13    7
## [3,]    8    7   13
print(t(matrix_A))
##      [,1] [,2] [,3]
## [1,]    5   13    8
## [2,]   12   13    7
## [3,]    4    7   13

$A^TA:$

print(t(matrix_A) %*% matrix_A)
##      [,1] [,2] [,3]
## [1,]  258  285  215
## [2,]  285  362  230
## [3,]  215  230  234

$AA^T:$

print(matrix_A %*% t(matrix_A))
##      [,1] [,2] [,3]
## [1,]  185  249  176
## [2,]  249  387  286
## [3,]  176  286  282

The example above shows that generally, the products of matrix multiplication are not equal when multiplication order is inversed.

#### Part 2

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 is true when the transpose of A is equal to A.

Demonstration:

matrix_B = matrix(c(1,0,1,0,1,0,1,0,1), nrow = 3, ncol = 3)
matrix_B
##      [,1] [,2] [,3]
## [1,]    1    0    1
## [2,]    0    1    0
## [3,]    1    0    1
matrix_B %*% t(matrix_B) == t(matrix_B) %*% matrix_B
##      [,1] [,2] [,3]
## [1,] TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE

### 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.

To solve this question, I used an algorithm from this site.

lu <- function(matrix){

n = nrow(A)

lower = matrix((c(1:n)*0), nrow=n, ncol=n)
upper = matrix((c(1:n)*0), nrow=n, ncol=n)

for(i in (1:n)) {
for(k in (i:n)) {
sum = 0
for(j in (1:i)) {
sum = sum + (lower[i,j] * upper[j, k])
}
upper[i, k] = A[i, k] - sum
}
for(k in (i:n)) {
if(i == k) {
lower[i, i] = 1
} else {
sum = 0
for(j in (1:i)) {
sum = sum + (lower[k, j] * upper[j, i])
}
lower[k, i] = (A[k, i] - sum) / upper[i, i]
}
}
}

return(list(lower, upper))
}

Generate a random 3x3 matrix:

A <- matrix(sample(1:20, 9, replace = TRUE), nrow = 3, ncol = 3)
print(A)
##      [,1] [,2] [,3]
## [1,]    3   16    6
## [2,]    3   14   16
## [3,]    3    4   19

The function returns the following lower form matrix:

#lower:
lu(A)[[1]]
##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    1    1    0
## [3,]    1    6    1

The function returns the following upper form matrix:

#upper:
lu(A)[[2]]
##      [,1] [,2] [,3]
## [1,]    3   16    6
## [2,]    0   -2   10
## [3,]    0    0  -47

Test that the product of the lower and upper form matrices is equal to the original matrix:

#test:
lu(A)[[1]] %*% lu(A)[[2]] == A
##      [,1] [,2] [,3]
## [1,] TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE