The following document pertains to assignment#3 for CUNY DAT605 - Foundamentals of Computational Mathematics.
Given the following Matrix A, what is the rank of A:
\(A\quad =\quad \begin{bmatrix} 1 & 2 & 3 & 4\\ -1 & 0 & 1 & 3\\ 0 & 1 & -2 & 1 \\ 5 & 4 & -2 & -3 \end{bmatrix}\)
The rank of Matrix A is the number of pivots. In order to determine this, we will need to place A in row reduction form. The R code below will do so and store all the pivots into a list. The lenght of the list will give us the rank of A. We will use previously written R code to create a function that will return the rank of an input matrix A and its Upper Triangular matrix. We will verify our results by using R built in functions.
# Helper Function to swap rows of matrix
swap_rows <-function(A, m, n){
temp <- A[m,]
A[m,] <- A[n,]
A[n,] <- temp
return(A)
}
# Helper function to find pivot
find_pivot <- function (A, r, c){
# Initialize return variables and processing variables
swap <- FALSE
p <- 0
swap_r <- 0
loop <- TRUE
i <- r
#loop through each of matrix and find non-zero pivot point for column c
while(loop){
if(A[i,c] != 0){
loop <- FALSE
p<-A[i,c]
if(i>r){
swap_r <- i
swap <- TRUE
} # end of inner if statement
} # end of outer if statement
i <- i + 1 #increment row
if (i > nrow(A)){
loop <- FALSE
}
} # end of while loop
return(list(p, swap, swap_r))
} # end of function
# Main function to Solve equation (3x3)
find_rank_matrix <- function (A){
# Validate input parameters, A, b, and whether row(A)==length(b)
if(missing(A)){
stop("Need to specify matrix A in equation Ax = b.")
}
if(nrow(A) != ncol(A)){
stop("Needs A to be square matrix.")
}
# store nrow and ncol for matrix A for reference
num_rows <- nrow(A)
num_col <- ncol(A)
# store Matrix and Vector in temporary variables
U <- A
# initialise an empty list
p_list <- list()
#-----------------#
# Build Upper-Triangular Matrix
# Initialize colum cursor
c <- 1
while (c <= num_col){
# Initialize row cursor
r <- c
# find pivot point
l_result <- find_pivot (U, r, c)
p <- unlist(l_result[1])
swap_indicator <- unlist(l_result[2])
swap_row <- unlist(l_result[3])
# Validate that pivot point is found
if (p==0){
text <- "No pivot point found in column"
txt_col <- as.character(c)
msg <- paste(text,txt_col)
stop(msg)
}
# if pivot point found, check for required swap
if(swap_indicator){
U <- swap_rows(U,r,swap_row)
}
# Add pivot point to pivot list
p_list[c] <- p
# Proceed with elimination for each rows
i <- r + 1
while (i <= num_rows){
# Determine multiplier
m = U[i,c]/p
U[i, ] <- U[i, ] - m*U[r, ]
i <- i + 1
} # end of for while for rows
c <- c + 1
} # end of while loop for columns
#------------#
return(list(length(p_list), U))
}
A <- matrix(c(1,2,3,4, -1,0,1,3,0,1, -2, 1, 5, 4, -2, -3),nrow=4, byrow = TRUE)
l_result <- find_rank_matrix(A)
rank <- l_result[[1]]
reduce_matrix <- l_result[[2]]
reduce_matrix## [,1] [,2] [,3] [,4]
## [1,] 1 2 3 4.000
## [2,] 0 2 4 7.000
## [3,] 0 0 -4 -2.500
## [4,] 0 0 0 1.125#Using build in function
y <- qr(A)Based on the reduce row form matrix, the rank of A is: 4
We can verify our result using the built-in R function. Rank of A is 4
Given an mxn matrix where m > n, what can be the maximum rank? The minimum rank, assuming that the matrix is non-zero.
If a matrix M is rectangular of dimensions mxn and m > n, then the maximum rank for M = n (the smaller of its dimension). The minimum rank for a non-zero matrix will be 1 (this implies that all its columns are linear combination of the others).
Given teh following matrix B, what is the rank of B.
\(B\quad =\quad \begin{bmatrix} 1 & 2 & 1 \\ 3 & 6 & 3 \\ 2 & 4 & 2 \end{bmatrix}\)
B is a 3x3 matrix hence its maximum rank would be 3, however, it is easy to see that all the columns in B are linear combination of column 1.. c2 = 2c1, c3=1c1. Hence the rank of B = 1
B <- matrix (c(1, 3, 2, 2, 6, 4, 1, 3, 2), nrow=3, byrow = FALSE)
y <- qr(B)
y$rank## [1] 1\(A\quad =\quad \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix}\)
\(\lambda\) is an eigenvalues of matrix A
\(\Leftrightarrow \quad A\cdot \vec { v } \quad =\quad \lambda \vec { v }\) for some non-zero \(\vec { v }\)
\(\Leftrightarrow \quad A\cdot \vec { v } -\quad \lambda { I }_{ 3 }\cdot \vec { v } \quad =\quad \vec { 0 }\)
\(\Leftrightarrow \quad (A\quad -\quad \lambda { I }_{ 3 })\cdot \vec { v } \quad =\quad \vec { 0 }\) for some non-zero \(\vec { v }\)
\(\Leftrightarrow \quad det(A\quad -\quad \lambda { I }_{ 3 })\quad =\quad 0\)
Let us write the matrix \(A\quad -\quad \lambda { I }_{ 3 }\)
\(A\quad -\quad \lambda { I }_{ 3 }\quad =\quad \begin{bmatrix} 1-\lambda & 2 & 3 \\ 0 & 4-\lambda & 5 \\ 0 & 0 & 6-\lambda \end{bmatrix}\)
\(det(A\quad -\quad \lambda { I }_{ 3 })\quad =\quad (1-\lambda )\begin{vmatrix} 4-\lambda & 5 \\ 0 & 6-\lambda \end{vmatrix}\quad -\quad 2\begin{vmatrix} 0 & 5 \\ 0 & 6-\lambda \end{vmatrix}\quad +\quad 3\begin{vmatrix} 0 & 4-\lambda \\ 0 & 0 \end{vmatrix}\quad\)
\(det(A\quad -\quad \lambda { I }_{ 3 })\quad =\quad (1-\lambda )[(4-\lambda )(6-\lambda )\quad -\quad 0]\quad -\quad 2(0\quad -\quad 0)\quad +\quad 3(0\quad -\quad 0)\)
\(det(A\quad -\quad \lambda { I }_{ 3 })\quad =\quad (1-\lambda )(4-\lambda )(6-\lambda )\) factor form of characteristic polynomial
\(det(A\quad -\quad \lambda { I }_{ 3 })\quad =\quad (1-\lambda )(24\quad -\quad 4\lambda \quad -\quad 6\lambda \quad +\quad { \lambda }^{ 2 })\quad =\quad 24\quad -\quad \quad 10\lambda \quad +\quad { \lambda }^{ 2 }\quad -\quad 24\lambda \quad +\quad 10{ \lambda }^{ 2 }\quad -\quad { \lambda }^{ 3 }\quad =\quad 24\quad -\quad 34\lambda \quad +\quad 11{ \lambda }^{ 2 }\quad -\quad { \lambda }^{ 3 }\)
\(det(A\quad -\quad \lambda { I }_{ 3 })\quad =\quad 0\quad \Leftrightarrow \quad (1\quad -\quad \lambda )(4\quad -\quad \lambda )(6\quad -\quad \lambda )\quad =\quad 0\)
\(det(A\quad -\quad \lambda { I }_{ 3 })\quad =\quad 0\quad \Leftrightarrow \quad \lambda \quad =\quad 1,\quad \lambda \quad =\quad 4,\quad or\quad \lambda \quad =\quad 6\)
For each eigenvalues of A, we will find the eigenvector by finding the vector \(\vec { v }\) such that:
\((A-\lambda { I }_{ 3 })\cdot \vec { v } =\quad 0\)
Substituing \(\lambda \quad =\quad 1\), we get:
\((A\quad -\quad 1{ I }_{ 3 })\cdot \vec { v } \quad =\quad \begin{bmatrix} 1-1 & 2-0 & 3-0 \\ 0-0 & 4-1 & 5-0 \\ 0-0 & 0-0 & 6-1 \end{bmatrix}\cdot \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad \begin{bmatrix} 0 & 2 & 3 \\ 0 & 3 & 5 \\ 0 & 0 & 5 \end{bmatrix}\cdot \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad \vec { 0 }\)
We get the following equations:
(1) \(0{ v }_{ 1 }\quad +\quad 2{ v }_{ 2 }\quad +\quad 3{ v }_{ 3 }\quad =\quad 0\)
(2) \(0{ v }_{ 1 }\quad +\quad 3{ v }_{ 2 }\quad +\quad 5{ v }_{ 3 }\quad =\quad 0\)
(3) \(0{ v }_{ 1 }\quad +\quad 0{ v }_{ 2 }\quad +\quad 5{ v }_{ 3 }\quad =\quad 0\)
From these we get; \({ v }_{ 2 }\quad =\quad { v }_{ 3 }\quad =\quad 0\quad and\quad { v }_{ 1 }\quad =\quad t\)
EigenSpace for \(\lambda \quad =\quad 1\) denoted \({ E }_{ \lambda =1 }\) can be written as follows:
\({ E }_{ \lambda =1 }\quad \left\{ \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad t\left[ \begin{matrix} 1 \\ 0 \\ 0 \end{matrix} \right] ,\quad for\quad all\quad t\quad \in \quad R \right\}\)
where \(\vec { i } =\quad \left[ \begin{matrix} 1 \\ 0 \\ 0 \end{matrix} \right]\) is the eigenvector.
Substituing \(\lambda \quad =\quad 4\), we get:
\((A\quad -\quad 4{ I }_{ 3 })\cdot \vec { v } \quad =\quad \begin{bmatrix} 1-4 & 2-0 & 3-0 \\ 0-0 & 4-4 & 5-0 \\ 0-0 & 0-0 & 6-4 \end{bmatrix}\cdot \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad \begin{bmatrix} -3 & 2 & 3 \\ 0 & 0 & 5 \\ 0 & 0 & 2 \end{bmatrix}\cdot \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad \vec { 0 }\)
We get the following equations:
(1) \(-3{ v }_{ 1 }\quad +\quad 2{ v }_{ 2 }\quad +\quad 3{ v }_{ 3 }\quad =\quad 0\)
(2) \(0{ v }_{ 1 }\quad +\quad 0{ v }_{ 2 }\quad +\quad 5{ v }_{ 3 }\quad =\quad 0\)
(3) \(0{ v }_{ 1 }\quad +\quad 0{ v }_{ 2 }\quad +\quad 2{ v }_{ 3 }\quad =\quad 0\)
From these we get; \(-3{ v }_{ 1 }\quad +\quad 2{ v }_{ 2 }\quad +\quad 3{ v }_{ 3 }\quad =\quad 0\quad and\quad { v }_{ 3 }\quad =\quad 0\)
\(-3{ v }_{ 1 }\quad +\quad 2{ v }_{ 2 }\quad =\quad 0\)
\({ v }_{ 2 }\quad =\quad \frac { 3 }{ 2 } { v }_{ 1 }\),
\(if\quad { v }_{ 1 }\quad =\quad t,\quad then\quad we\quad have\quad { v }_{ 2 }\quad =\quad \frac { 3 }{ 2 } t\)
EigenSpace for \(\lambda \quad =\quad 4\) denoted \({ E }_{ \lambda =4 }\) can be written as follows:
\({ E }_{ \lambda =4 }\quad \left\{ \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad t\left[ \begin{matrix} 1 \\ \frac { 3 }{ 2 } \\ 0 \end{matrix} \right] ,\quad for\quad all\quad t\quad \in \quad R \right\}\)
where \(\vec { v } =\quad \left[ \begin{matrix} 1 \\ \frac { 3 }{ 2 } \\ 0 \end{matrix} \right]\) is the eigenvector.
Substituing \(\lambda \quad =\quad 6\), we get:
\((A\quad -\quad 6{ I }_{ 3 })\cdot \vec { v } \quad =\quad \begin{bmatrix} 1-6 & 2-0 & 3-0 \\ 0-0 & 4-6 & 5-0 \\ 0-0 & 0-0 & 6-6 \end{bmatrix}\cdot \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad \begin{bmatrix} -5 & 2 & 3 \\ 0 & -2 & 5 \\ 0 & 0 & 0 \end{bmatrix}\cdot \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad \vec { 0 }\)
We get the following equations:
(1) \(-5{ v }_{ 1 }\quad +\quad 2{ v }_{ 2 }\quad +\quad 3{ v }_{ 3 }\quad =\quad 0\)
(2) \(0{ v }_{ 1 }\quad +\quad -2{ v }_{ 2 }\quad +\quad 5{ v }_{ 3 }\quad =\quad 0\)
(3) \(0{ v }_{ 1 }\quad +\quad 0{ v }_{ 2 }\quad +\quad 0{ v }_{ 3 }\quad =\quad 0\)
From these we get;
(1) \(-5{ v }_{ 1 }\quad +\quad 2{ v }_{ 2 }\quad +\quad 3{ v }_{ 3 }\quad =\quad 0\)
(2) \(-2{ v }_{ 2 }\quad +\quad 5{ v }_{ 3 }\quad =\quad 0\)
from (2), we get \({ v }_{ 3 }\quad =\quad \frac { 2 }{ 5 } { v }_{ 2 }\), substituing \({ v }_{ 3 }\) back in (1) we obtain:
\(-5{ v }_{ 1 }\quad +\quad 2{ v }_{ 2 }\quad +\quad 3(\frac { 2 }{ 5 } { v }_{ 2 })\quad =\quad -5{ v }_{ 1 }\quad +\quad \frac { 10\quad +\quad 6 }{ 5 } { v }_{ 2 }\quad =\quad 0\), hence we have for \({v}_{2}\)
\({ v }_{ 2 }\quad =\quad \frac { 25 }{ 16 } { v }_{ 1 }\)
\(If\quad { v }_{ 1 }\quad =\quad t\), then \({ v }_{ 2 }\quad =\quad \frac { 25 }{ 16 } t\quad and\quad { v }_{ 3 }\quad =\quad \frac { 5 }{ 8 } t\)
EigenSpace for \(\lambda \quad =\quad 6\) denoted \({ E }_{ \lambda =6 }\) can be written as follows:
\({ E }_{ \lambda =6 }\quad \left\{ \left[ \begin{matrix} { v }_{ 1 } \\ { v }_{ 2 } \\ { v }_{ 3 } \end{matrix} \right] \quad =\quad t\left[ \begin{matrix} 1 \\ \frac { 55 }{ 16 } \\ \frac { 5 }{ 8 } \end{matrix} \right] ,\quad for\quad all\quad t\quad \in \quad R \right\}\)
where \(\vec { v } =\quad \left[ \begin{matrix} 1 \\ \frac { 55 }{ 16 } \\ \frac { 5 }{ 8 } \end{matrix} \right]\) is the eigenvector.