DATA (IS) 605 FUNDAMENTALS OF COMPUTATIONAL MATHEMATICS - FALL 2016 - ASSIGNMENT 4

Problem Set 1

(1) Verify using R that SVD and Eigenvalues are related

Given: \(A = \left[ \begin{array}{ccc} 1 & 2 & 3 \\ -1 & 0 & 4 \\ \end{array}\right]\)

a) Use R to compute \(X = AA^T\) and \(Y = A^TA\)

A <- matrix(c(1, -1, 2, 0, 3, 4), nrow=2)
A

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

X <- A%*%t(A)
Y <- t(A)%*%A
X

##      [,1] [,2]
## [1,]   14   11
## [2,]   11   17

Y

##      [,1] [,2] [,3]
## [1,]    2    2   -1
## [2,]    2    4    6
## [3,]   -1    6   25

b) Compute the eigenvalues and eigenvectors of X and Y using the built-in commands in R

x <- eigen(X)
y <- eigen(Y)
x$val

## [1] 26.601802  4.398198

x$vec

##           [,1]       [,2]
## [1,] 0.6576043 -0.7533635
## [2,] 0.7533635  0.6576043

y$val

## [1] 2.660180e+01 4.398198e+00 1.058982e-16

y$vec

##             [,1]       [,2]       [,3]
## [1,] -0.01856629 -0.6727903  0.7396003
## [2,]  0.25499937 -0.7184510 -0.6471502
## [3,]  0.96676296  0.1765824  0.1849001

c) Compute the left-singular, singular values, and right-singular vectors of A using the svd command

asvd <- svd(A)
left <- asvd$u
left

##            [,1]       [,2]
## [1,] -0.6576043 -0.7533635
## [2,] -0.7533635  0.6576043

singular <- asvd$d
singular

## [1] 5.157693 2.097188

right <- asvd$v
right

##             [,1]       [,2]
## [1,]  0.01856629 -0.6727903
## [2,] -0.25499937 -0.7184510
## [3,] -0.96676296  0.1765824

d) Examine the two sets of singular vectors and show that they are indeed eigen vectors of X and Y

x$vec

##           [,1]       [,2]
## [1,] 0.6576043 -0.7533635
## [2,] 0.7533635  0.6576043

left

##            [,1]       [,2]
## [1,] -0.6576043 -0.7533635
## [2,] -0.7533635  0.6576043

y$vec

##             [,1]       [,2]       [,3]
## [1,] -0.01856629 -0.6727903  0.7396003
## [2,]  0.25499937 -0.7184510 -0.6471502
## [3,]  0.96676296  0.1765824  0.1849001

right

##             [,1]       [,2]
## [1,]  0.01856629 -0.6727903
## [2,] -0.25499937 -0.7184510
## [3,] -0.96676296  0.1765824

e) Show that the eigen values of both X and Y are the same and are squares of the non-zero singular values of A

We can see from above that the eigen values for X are 26.6 and 4.4 rounding to the 1st decimal. The eigen values for Y are the same after we covert from scientific notation (2.660180e+01 = 26.6). The third eigen value of Y is 1.059e-16, which is almost zero.

The non-zero sigular values of A are from above: 5.16 and 2.10. The squares are 26.6 and 4.4, which match the eigen values for X.

5.16 * 5.16

## [1] 26.6256

2.1 * 2.1

## [1] 4.41

Problem Set 2

write a function B = myinverse(A) to compute the inverse of a well-conditioned full-rank square matrix using co-factors

From section 1, we compute its determinant and all its co-factors. We take the transpose of the co-factor matrix and divide it by the determinant of the matrix to get the inverse. \(A^{-1} = C^T/\det(A)\)

myinverse <- function(A) {
  # Find the dimension and determinant of the matrix; make co-factor matrix
  adim <- dim(A)[1]
  adet <- det(A)
  C <- A
  
  # Go through all the rows
  for (i in 1: adim) {
    
    # Go through all the columns
    for (j in 1: adim) {
       # Find determinate for sub-matrix
       D <- A[-i, -j]
       ddet <- det(D)
       # Make cofactor matrix element
       C[i, j] <- (-1)^(i+j) * ddet
    }
  }
  B <- t(C)
  B <- B / adet
  return(B)
}

mat <- matrix(c(1, 2, 3, 1, 1, 1, 2, 0, 1),nrow=3)
mat

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

invmat <- myinverse(mat)
invmat

##            [,1]       [,2]       [,3]
## [1,] -0.3333333 -0.3333333  0.6666667
## [2,]  0.6666667  1.6666667 -1.3333333
## [3,]  0.3333333 -0.6666667  0.3333333

invmat %*% mat

##               [,1]          [,2] [,3]
## [1,]  1.000000e+00  0.000000e+00    0
## [2,]  4.440892e-16  1.000000e+00    0
## [3,] -2.220446e-16 -5.551115e-17    1

solve(mat)

##            [,1]       [,2]       [,3]
## [1,] -0.3333333 -0.3333333  0.6666667
## [2,]  0.6666667  1.6666667 -1.3333333
## [3,]  0.3333333 -0.6666667  0.3333333