DCraig_Assignment2

Problem Set 1

1. Show that \(A^TA \neq AA\), in general. (Proof and demonstration.)

Definitions:

Let’s start by naming the definition we will use.

Definition MM: Suppose A is an m × n matrix and B1, B2, B3, . . . , Bp are the columns of an n × p matrix B. Then the matrix product of A with B is the m×p matrix where column i is the matrix-vector product ABi. Symbolically, \[AB = A[B_1 | B_2| B_3| ...| B_p] = [AB_1 | AB_2 | AB_3 | ... |AB_p] \]

Definition MVP: Matrix-Vector Product, the product of a matrix and a vector is equal to a linear combination of products from the vector’s values and a matrix’s columns.

Definition TM: Given an m × n matrix A, its transpose is the n × m matrix At given by

\[[A^T]_{ij} = [A]_{ji} , 1 \leq i \leq n, 1 \leq j \leq m\]

Establishing \(AA^T\)

Let’s say we have a 2x2 matrix, A. \[A = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \]

By Definition MM, we know that \(AA\) is written as: \[AA = [Aa1|Aa2]\]

and that Matrix Vector Product by Definition MVP can be written as: Aa1 = a* \(\begin{bmatrix}a \\ c\end{bmatrix}\) \(|\) c*\(\begin{bmatrix}b \\d\end{bmatrix}\) = \(\begin{bmatrix}a^2 + cb \\ ac + cd\end{bmatrix}\)

Aa2= b* \(\begin{bmatrix}a \\ c\end{bmatrix}\) \(|\) d*\(\begin{bmatrix}b \\d\end{bmatrix}\) = \(\begin{bmatrix}ba + db \\ bc + d^2\end{bmatrix}\)

Thus, AA = \[\begin{bmatrix} a^2 +cb & ba +db \\ ac + cd & bc + d^2 \end{bmatrix}\]

Now that we’ve shown what AA is equal to, let’s transpose it:

With Definition TM, we know that \(AA^t\) can is: \[ AA^T = \begin{bmatrix} a^2 +cb & ac +cd \\ ba+db & bc+dc^2 \end{bmatrix} \]

Establishing \(A^TA\)

Let’s begin with establishing \(A^T\) \[A^T = \begin{bmatrix} a & c \\ b & d \end{bmatrix} \] Then we move to matrix multiplication using the same definitions as earlier, our result is:

\[ A^TA = \begin{bmatrix} a & c \\ b & d \end{bmatrix} * \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} a^2 + ac + ca + c^2 & ab + ad + cb + cd \\ ba + bc + da + dc & b^2 + bd + db + d^2 \end{bmatrix} \]

Comparison

Let’s recall our earlier result for \(AA^T\) \[ AA^T = \begin{bmatrix} a^2 +cb & ac +cd \\ ba+db & bc+dc^2 \end{bmatrix} \] We can clearly see that these two are are not equal.

2. 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).

This condition is true when the matrix is symmetric (which also begets it being square.)

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.

Recall that LU Decomposition’s goal is to find a lower triangular matrix (L) and an upper triangular matrix (U) that when multiplied create a square matrix A.

For this method to work, the following must be met:

  1. The main diagonal of \(L\) must be 1 and the values above that diagonal are 0 and vice versa for \(U\).

  2. \(A\) must be able to be reduced to row-echelon form into U without interchanging any rows.

  3. \(L\) and \(U\) are not unique

  4. If doing by hand, specifically for the shortcut method, we will use the opposites of the multipliers used in row operations to obtain U to build L

  5. The determinant of the matrix to be decomposed must not be singular/non-invertible (since if it was, we wouldn’t be able to find a linear transformation that could apply[ in this case L] to U to create the original matrix)

Note that using lu from the library Matrix creates PLU instead of just LU, but the P is just a linear transformation if it is relevant.

library(Matrix)

diag_values <- c(1,2,3,4,5)

mat <- diag(diag_values)
det(mat)
## [1] 120
if (det(mat) !=0) {
  print("The matrix is non-singular.")
  lu_mat <- lu(mat)
  lu_mat
  expand(lu_mat)
} else {
  print("The matrix is singular and non-invertible and cannot be LU decomposed.")
}
## [1] "The matrix is non-singular."
## $L
## 5 x 5 Matrix of class "dtrMatrix" (unitriangular)
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    1    .    .    .    .
## [2,]    0    1    .    .    .
## [3,]    0    0    1    .    .
## [4,]    0    0    0    1    .
## [5,]    0    0    0    0    1
## 
## $U
## 5 x 5 Matrix of class "dtrMatrix"
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    1    0    0    0    0
## [2,]    .    2    0    0    0
## [3,]    .    .    3    0    0
## [4,]    .    .    .    4    0
## [5,]    .    .    .    .    5
## 
## $P
## 5 x 5 sparse Matrix of class "pMatrix"
##               
## [1,] | . . . .
## [2,] . | . . .
## [3,] . . | . .
## [4,] . . . | .
## [5,] . . . . |