Gershgorin Disks - Portfolio

Gershgorin Disks #

Implement functions to calculate Greshgorin Disks and plot them on a cartesian plane.

.rmd knitted with execution results available for download here

Write functions deleted_row_sum and#

deleted_col_sum

Both functions will take a square matrix M of dim = n as a parameter and each will return a vector of all the row/col sums.

Each row/col sum is the sum of the absolute values in the all the entries in the ith row/col excluding the ‘deleted’ ith entry.

1
deleted_row_sum = function(M){
2
  # ensure M is square
3
  if(dim(M)[1] != dim(M)[2]){
4
    # return error, quit function
5
    stop("Matrix given is not square.")
6
  }
7
  # continue
8
  # result is empty vector of size 'n x 1'
9
  res = matrix(nr=dim(M)[1], nc=1)
10
  for(i in 1:dim(M)[1]){
11
    deleted_i = 0
12
    # sum up all the values in ith row, excluding the ith value
13
    # deleted_i = sum(abs(M[i])) - abs(M[i,i])
14
    for(j in 1:dim(M)[1]){
15
      if(j != i){
16
        deleted_i = deleted_i + abs(M[i,j])
17
      } # else to do nothing
18
      res[i] = deleted_i
19
    }
20
  }
21
  return(res)
22
}

1
deleted_col_sum = function(M){
2
  # ensure M is square
3
  if(dim(M)[1] != dim(M)[2]){
4
    # return error, quit function
5
    stop("Matrix given is not square.")
6
  }
7
  # continue
8
  # result is empty vector of size 'n x 1'
9
  res = matrix(nr=dim(M)[1], nc=1)
10
  for(i in 1:dim(M)[1]){
11
    # sum up all the values in ith col, then cancel out ith value
12
    deleted_i = 0
13
    for(j in 1:dim(M)[1]){
14
      if(j != i){
15
        deleted_i = deleted_i + abs(M[j,i])
16
      } # else to do nothing
17
      res[i] = deleted_i
18
    }
19
    res[i] = deleted_i
20
  }
21
  return(res)
22
}

Write function gershgorin_disks#

Takes a square matrix M

Returns a 2-tuple of dataframes

1 dataframe is row_disks, the other is col_disks, so return is c(row_disks, col_disks)

both dataframes contain a column called ‘center’ containing the center coordinates of the disk and another column called ‘radius’ containing the radius of each disk.

The center of each disk in row_disk or col_disk is the deleted ith value, specifically the values on the main diagonal.

The radius of each disk is the deleted_row/col_sum associated with each center.

1
gershgorin_disks = function(M){
2
  # ensure M is square
3
  if(dim(M)[1] != dim(M)[2]){
4
    # return error, quit function
5
    stop("Matrix given is not square.")
6
  }
7
  # continue
8

9
  # declare return values
10
  row_disks = data.frame(matrix(nr=dim(M)[1],nc=2))
11
  col_disks = data.frame(matrix(nr=dim(M)[1],nc=2))
12
  colnames(row_disks) = c("center", "radius")
13
  colnames(col_disks) = c("center", "radius")
14

15

16
  # define return values
17
  row_disks$radius = deleted_row_sum(M)
18
  col_disks$radius = deleted_col_sum(M)
19

20
  row_disks$center = diag(M)
21
  col_disks$center = diag(M)
22
  return(list(row_disks, col_disks))
23
}

Write function plot_gg_disks#

Takes square matrix ‘M’

Returns two plots on with the real numbers on the x-axis, and imaginary numbers on the y-axis

Will plot both the ‘row_disks’ and the ‘col_disks’ from the gershgorin_disks function

Use distinct colors for the row disks and the col disks, so you know which is which

Will not be using fill when coloring the disks, due to the possibility of overlap, instead will just be doing an outline, which is technically not accurate, but I figured as long as I acknowledged it, the increase in clarity would be worth it.

1
plot_gg_disks = function(M){
2
  # ensure M is square
3
  if(dim(M)[1] != dim(M)[2]){
4
    # return error, quit function
5
    stop("Matrix given is not square.")
6
  }
7
  # continue
8
  disks = gershgorin_disks(M)
9
  # print(disks)
10
  # plot row_disk
11

12
  # get data to plot
13
  r_x = Re(as.data.frame(disks[1])$center)
14
  r_y = Im(as.data.frame(disks[1])$center)
15
  r_r = Re(as.data.frame(disks[1])$radius)
16
  # * Since radius is the sum of absolute values, |i| = 1, so it's always Real
17
  # but, just to be sure
18
  c_x = Re(as.data.frame(disks[2])$center)
19
  c_y = Im(as.data.frame(disks[2])$center)
20
  c_r = Re(as.data.frame(disks[2])$radius)
21

22
  # construct dataframes to plot
23
  circ1 = data.frame(
24
    x = r_x,
25
    y = r_y,
26
    r = r_r
27
  )
28
  circ2 = data.frame(
29
    x = c_x,
30
    y = c_y,
31
    r = c_r
32
  )
33

34
  print("row disks are:")
35
  print(circ1)
36
  print("col disks are:")
37
  print(circ2)
38

39
  # plot both row and col disks
40
  ggplot() +
41
    geom_circle(aes(x0 = x, y0 = y, r = r), data=circ1, color="red") +
42
    geom_circle(aes(x0 = x, y0 = y, r = r), data=circ2, color="blue") +
43
    labs(x="Real Numbers", y="Imaginary Numbers") + coord_fixed()
44

45

46
}

Write functions make_row_stochastic_matrix and make_col_stochastic_matrix#

Start by making a helper function to normalize vectors

1
normalize = function(vec){
2
  return(vec / sqrt(sum(vec^2)))
3
}

A matrix is row stochastic if:

No entry is equal to zero
All the entries in a row equal to 1
Non-Negative Matrix (all entries positive)
Create a square matrix of size ‘n’

1
make_row_stochastic_matrix = function(n){
2
  # n x n matrix, all NA
3
  mat = matrix(nc=n,nr=n)
4
  # generate random n x 1 vectors, all normalized
5
  for(i in c(1:n)){
6
    mat[i,] = normalize(runif(n, 0, 2))
7
  }
8
  return(mat)
9
}

A matrix is col stochastic if:

No entry is equal to zero
All the entries in a col equal to 1
Non-Negative Matrix (all entries positive)
Create a square matrix of size ‘n’

1
make_col_stochastic_matrix = function(n){
2
  # n x n matrix, all NA
3
  mat = matrix(nc=n,nr=n)
4
  # generate random n x 1 vectors, all normalized
5
  for(i in c(1:n)){
6
    mat[,i] = normalize(runif(n, 0, 2))
7
  }
8
  return(mat)
9
}

Use plot_gg_disks to plot the disks associated with the matrices in Q1#

1
# ggplot2 extension package that has geom_circle in it
2
if (!require("ggforce")) {
3
    install.packages("ggforce")
4
    library(ggforce)
5
}

1
## Loading required package: ggforce

1
## Loading required package: ggplot2

1
## Warning: package 'ggplot2' was built under R version 4.3.3

1
A = matrix(c(1, -1, 1, -2), nc=2, nr=2)
2
B = matrix(c(2, -1, 1i, 1, 1+2i, 0, 1, 2, -1), nc=3, nr=3)
3
plot_gg_disks(A)

1
## [1] "row disks are:"
2
##    x y r
3
## 1  1 0 1
4
## 2 -2 0 1
5
## [1] "col disks are:"
6
##    x y r
7
## 1  1 0 1
8
## 2 -2 0 1

1
plot_gg_disks(B)

1
## [1] "row disks are:"
2
##    x y r
3
## 1  2 0 2
4
## 2  1 2 3
5
## 3 -1 0 1
6
## [1] "col disks are:"
7
##    x y r
8
## 1  2 0 2
9
## 2  1 2 1
10
## 3 -1 0 3

Plot Random Stochastic Matrices#

1
S1 = make_row_stochastic_matrix(5)
2
S1

1
##           [,1]      [,2]      [,3]       [,4]      [,5]
2
## [1,] 0.5148093 0.5459863 0.3979048 0.50716414 0.1460365
3
## [2,] 0.4766335 0.8404548 0.1053752 0.06975258 0.2246930
4
## [3,] 0.1617591 0.0160156 0.0472864 0.67656080 0.7166638
5
## [4,] 0.5287457 0.5341048 0.1808659 0.33785498 0.5369372
6
## [5,] 0.2764034 0.4884809 0.5626943 0.59682373 0.1102913

1
S2 = make_col_stochastic_matrix(5)
2
S2

1
##           [,1]       [,2]      [,3]      [,4]       [,5]
2
## [1,] 0.5581630 0.61107192 0.1159964 0.4579087 0.07239551
3
## [2,] 0.1555763 0.38608039 0.3032119 0.6188590 0.56072628
4
## [3,] 0.3065470 0.08878685 0.1543963 0.1277550 0.52300009
5
## [4,] 0.5513180 0.60798285 0.6080962 0.1969303 0.55387090
6
## [5,] 0.5160692 0.31623850 0.7078051 0.5934899 0.31629554

1
plot_gg_disks(S1)

1
## [1] "row disks are:"
2
##           x y         r
3
## 1 0.5148093 0 1.5970917
4
## 2 0.8404548 0 0.8764543
5
## 3 0.0472864 0 1.5709993
6
## 4 0.3378550 0 1.7806536
7
## 5 0.1102913 0 1.9244023
8
## [1] "col disks are:"
9
##           x y        r
10
## 1 0.5148093 0 1.443542
11
## 2 0.8404548 0 1.584588
12
## 3 0.0472864 0 1.246840
13
## 4 0.3378550 0 1.850301
14
## 5 0.1102913 0 1.624330

1
plot_gg_disks(S2)

1
## [1] "row disks are:"
2
##           x y        r
3
## 1 0.5581630 0 1.257373
4
## 2 0.3860804 0 1.638373
5
## 3 0.1543963 0 1.046089
6
## 4 0.1969303 0 2.321268
7
## 5 0.3162955 0 2.133603
8
## [1] "col disks are:"
9
##           x y        r
10
## 1 0.5581630 0 1.529511
11
## 2 0.3860804 0 1.624080
12
## 3 0.1543963 0 1.735110
13
## 4 0.1969303 0 1.798013
14
## 5 0.3162955 0 1.709993

Gershgorin Disks#