1 Problem Set 1

You can think of vectors representing many dimensions of related information. For instance, Netfix might store all the ratings a user gives to movies in a vector. This is clearly a vector of very large dimensions (in the millions) and very sparse as the user might have rated only a few movies. Similarly, Amazon might store the items purchased by a user in a vector, with each slot or dimension representing a unique product and the value of the slot, the number of such items the user bought. One task that is frequently done in these settings is to find similarities between users. And, we can use dot-product between vectors to do just that. As you know, the dot-product is proportional to the length of two vectors and to the angle between them. In fact, the dot-product between two vectors, normalized by their lengths is called as the cosine distance and is frequently used in recommendation engines.

u = c(0.5, 0.5)
v = c(3, -4)
dot_product_uv <- dot(u,v)
dot_product_uv

## [1] -0.5

length_u <- sqrt(dot(u,u))
length_u

## [1] 0.7071068

length_v <- sqrt(dot(v,v))
length_v

## [1] 5

3*u-2*v

## [1] -4.5  9.5

theta <- acos(dot_product_uv/length_u/length_v)
theta  #in radian

## [1] 1.712693

theta/pi*180  #in degree

## [1] 98.1301

2 Problem Set 2

Set up a system of equations with 3 variables and 3 constraints and solve for x. Please write a function in R that will take two variables (matrix A & constraint vector b) and solve using elimination. Your function should produce the right answer for the system of equations for any 3-variable, 3-equation system. You don’t have to worry about degenerate cases and can safely assume that the function will only be tested with a system of equations that has a solution. Please note that you do have to worry about zero pivots, though. Please note that you should not use the built-in function solve to solve this system or use matrix inverses. The approach that you should employ is to construct an Upper Triangular Matrix and then back-substitute to get the solution. Alternatively, you can augment the matrix A with vector b and jointly apply the Gauss Jordan elimination procedure.

Please test it with the system below and it should produce a solution \(x\) = [-1.55, -0.32, 0.95]. \[\begin{bmatrix} 1 & 1 & 3\\ 2 & -1 & 5\\ -1 & -2 & 4 \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2}\\ x_{3}\end{bmatrix} = \begin{bmatrix} 1\\ 2\\ 6\end{bmatrix}\]

gaussjordan <- function(A,b){
  #assume pivot exists in all columns
  r1 <- TRUE; r2 <- TRUE; r3 <- TRUE
  
  #augment the matrix A with vector b
  A <- cbind(A, as.matrix(b))

  #find pivot in row 1 column 1
  pivot_1 <- A[1,1]
  if (pivot_1 == 0){
    A = A[c(2,3,1),]
    pivot_1 <- A[1,1]
    if (pivot_1 == 0){
      A = A[c(2,1,3),]
      pivot_1 <- A[1,1]
      if (pivot_1 == 0){
        r1 = FALSE  #pivot does not exist in first column
      }
    }
  }
  
  #if pivot1 exists in row 1 column 1
  if (r1) {
    #top row's leading entry becomes 1 (coef of x1)
    A[c(1),] <- A[c(1),]/pivot_1
    
    #eliminate x1 values in row2 and row3
    A[c(2),] = A[c(2),] - A[2,1]*A[c(1),]
    A[c(3),] = A[c(3),] - A[3,1]*A[c(1),]
  
    #find pivot in row 2 column 2
    pivot_2 <- A[2,2]
    if (pivot_2 == 0){
      A = A[c(1,3,2),]
      pivot_2 <- A[2,2]
      if (pivot_2 == 0)
        r2 = FALSE  #pivot does not exist in second column
    }
    
    #if pivot2 exists in row 2 column 2
    if (r2) {
      #2nd row's leading entry becomes 1 (coef of x2)
      A[c(2),] <- A[c(2),]/pivot_2
      
      #eliminate x2 value in row1 and row3
      A[c(1),] = A[c(1),] - A[1,2]*A[c(2),]
      A[c(3),] = A[c(3),] - A[3,2]*A[c(2),]
      
      if (A[3,3] != 0){
        #3rd row's leading entry becomes 1
        A[c(3),] <- A[c(3),]/A[3,3]
        
        #eliminate x3 value in row1 and row2
        A[c(1),] = A[c(1),] - A[1,3]*A[c(3),]
        A[c(2),] = A[c(2),] - A[2,3]*A[c(3),]
      }
      else
        r3 = FALSE
    }
    else { 
      #if pivot2 does not exist in 2nd column
      pivot_3 <- A[2,3]
      if (pivot_3 == 0){
        A = A[c(1,3,2),]
        pivot_3 <- A[2,3]
        if (pivot_3 == 0)
          r3 = FALSE  #pivot3 does not exist in 3rd column
      }
      
      if (r3) { 
        #if r3 exists in row 2 column 3
        #leading entry becomes 1 (coef of x3)
        A[c(2),] <- A[c(2),]/pivot_3
        
        #eliminate x3 value in row1 and row3
        A[c(1),] = A[c(1),] - A[1,3]*A[c(2),]
        A[c(3),] = A[c(3),] - A[3,3]*A[c(2),]
      }
    }
  }
  
  #if pivot1 does not exist column 1
  if (!(r1)) {
    #find pivot in second column
    pivot_2 <- A[1,2]
    if (pivot_2 == 0){
      A = A[c(2,3,1),]
      pivot_2 <- A[1,2]
      if (pivot_2 == 0){
        A = A[c(2,1,3),]
        if (pivot_2 == 0){
          r2 = FALSE  #pivot does not exist in 2nd column
          
          #find pivot3 in row 1 column 3
          pivot_3 <- A[1,3]
          if (pivot_3 == 0){
            A = A[c(2,3,1),]
            pivot_3 <- A[1,3]
            if (pivot_3 == 0){
              A = A[c(2,1,3),]
              if (pivot_3 == 0)
                r3 = FALSE  #pivot does not exist in all columns
            }
          }
          
          #if pivot exists in row 1 column 3
          if (r3) {
            #leading entry becomes 1 (coef of x3)
            A[c(1),] <- A[c(1),]/pivot_3
            
            #eliminate x3 value in row2 and row3
            A[c(2),] = A[c(2),] - A[2,3]*A[c(1),]
            A[c(3),] = A[c(3),] - A[3,3]*A[c(1),]
          }
        }
      }
    }
    
    #if pivot exists in row 1 column 2
    if (r2){
      pivot_2 <- A[1,2]
      #leading entry becomes 1 (coef of x2)
      A[c(1),] <- A[c(1),]/pivot_2
          
      #eliminate x2 value in row2 and row3
      A[c(2),] = A[c(2),] - A[2,2]*A[c(1),]
      A[c(3),] = A[c(3),] - A[3,2]*A[c(1),]
          
      #find pivot in row 2 column 3
      pivot_3 <- A[2,3]
      if (pivot_3 == 0){
        A = A[c(1,3,2),]
        pivot_2 <- A[2,3]
        if (pivot_3 == 0)
          r3 = FALSE #pivot does not exist in 3rd column
      }
          
      if (r3) {
        #if pivot exists in row 2 column 3
        #eliminate x3 value in row3
        A[c(3),] = A[c(3),] - A[3,3]*A[c(2),]
      }
    }
  }
  
  x <- A[,4]
  round(x,2)
}

#test the system
A <- matrix(c(1,1,3,2,-1,5,-1,-2,4), nrow=3, ncol=3, byrow=TRUE)
b <- c(1,2,6)
gaussjordan(A,b)

## [1] -1.55 -0.32  0.95