CECS 229 Programming Assignment #6

CECS 229 Programming Assignment #6


Submission Instructions:
To receive credit for this assignment you must submit to CodePost a Python script named pa6.py with your work by the due date.

Objectives:
Apply Gaussian Elimination to solve the system  Ax→=b→
 .
Use Lp -norm to calculate the error in a solution given by applying Gaussian elimination.
Use the REF of the augmented matrix for the system  Ax→=b→
  to determine if it has one solution, no solution, or infinitely-many solutions.
Determine the number of free variables that the system  Ax→=b→
  has if it has infinitely-many solutions.
Determine whether a set of column-vectors is linearly dependent by forming and solving a system of the form  Ax→=0→
 .
Problem 1
Copy-paste your implemented Matrix and Vec classes to the next cell. Then, complete the following tasks:

Add a method norm(self, p) to your Vec class so that if u is a Vec object, then u.norm(p) returns the  Lp
 -norm of vector u. Recall that the  Lp
 -norm of an  n
 -dimensional vector  u→
  is given by,  ||u||p=(∑ni=1|ui|p)1/p
 . Input p should be of the type int. The output norm should be of the type float.
Add a method ref(self) that applies Gaussian Elimination to create and return the Row Echelon Form of the current matrix. The output must be of the type Matrix. The method should NOT modify the contents of self.rowsp or self.colsp. It should create and return a new Matrix object.
Add a method rank(self) to your Matrix class so that if A is a Matrix object, then A.rank() returns the rank of A.
import math
 
# Putting up Vector class from the previous assignment
class Vec:
    def __init__(self, contents=[]):
        """
        Constructor defaults to empty vector
        INPUT: list of elements to initialize a vector object, defaults to empty list
        """
        self.elements = contents
        return
 
    def __abs__(self):
        """
        Overloads the built-in function abs(v)
        returns the Euclidean norm of vector v
        """
        # Variable to store the magnitude of the vector
        magnitude_vector = 0
        # Variable to store the sum of the squares of the elements in the vector
        vector_squares = []
        # Running through all the elements in the vector
        for element in self.elements:
            # Squaring the elements of the vector
            sum_of_squares = element ** 2
            # Appending the sum of the squares to the list
            vector_squares.append(sum_of_squares)
 
        # Square root of the sum of the squares of the elements in the vector
        magnitude_vector = math.sqrt(sum(vector_squares))
 
        return magnitude_vector  # Returning the magnitude of the vector
 
    def __add__(self, other):
        """Overloads the + operator to support Vec + Vec
        raises ValueError if vectors are not same length
        """
        # Conditional Statement to check whether vectors are of same length
        if len(self.elements) != len(other.elements):
            raise ValueError("Vectors must be same length")
        else:  # Run the following code once the condition is satisfied
            # Variable to store the sum of the vectors
            vector_sum = []
            # Running through all the elements in the vector
            for element in range(len(self.elements)):
                # Adding the elements of the vectors together
                sum_result = self.elements[element] + other.elements[element]
                # Appending the sum of the elements to the list
                vector_sum.append(sum_result)
 
        # Converting the list to a vector
        vector_sum = Vec(vector_sum)
 
        return vector_sum  # Returning the sum of the vectors
 
    def __sub__(self, other):
        """
        Overloads the - operator to support Vec - Vec
        Raises a ValueError if the lengths of both Vec objects are not the same
        """
        # Conditional Statement to check whether vectors are of same length
        if len(self.elements) != len(other.elements):
            raise ValueError("Vectors must be same length")
        else:  # Run the following code once the condition is satisfied
            # Variable to store the difference of the vectors
            vector_difference = []
            # Running through all the elements in the vector
            for element in range(len(self.elements)):
                # Subtracting the elements of the vectors together
                difference_result = self.elements[element] - other.elements[element]
                # Appending the difference of the elements to the list
                vector_difference.append(difference_result)
 
        # Converting the list to a vector
        vector_difference = Vec(vector_difference)
 
        return vector_difference  # Returning the difference of the vectors
 
    def __mul__(self, other):
        """Overloads the * operator to support
        - Vec * Vec (dot product) raises ValueError if vectors are not same length in the case of dot product
        - Vec * float (component-wise product)
        - Vec * int (component-wise product)
        """
        if type(other) == Vec:  # define dot product
            # Conditional Statement to check whether vectors are of same length
            if len(self.elements) != len(other.elements):
                raise ValueError("Vectors must be same length")
            else:  # Run the following code once the condition is satisfied
                # Variable to store the dot product of the vectors
                dot_product = 0
                # Running through all the elements in the vector
                for element in range(len(self.elements)):
                    # Multiplying the elements of the vectors each other
                    product_result = self.elements[element] * other.elements[element]
                    # Adding the product of the elements to the variable
                    dot_product += product_result
 
                return dot_product  # Returning the dot product
        elif type(other) == float or type(other) == int:  # scalar-vector multiplication
            # Variable to store the result of scalar-vector multiplication
            vector_product = []
            # Running a loop through all the elements in the vector
            for element in range(len(self.elements)):
                # Multiplying the each elements in the vector to the scalar value
                product_result = self.elements[element] * other
                # Appending the product of the elements to the list
                vector_product.append(product_result)
 
            # Converting the list to a vector
            vector_product = Vec(vector_product)
 
            return vector_product  # Returning the scalar-vector multiplication
 
    def __rmul__(self, other):
        """
        Overloads the * operation to support
            - float * Vec
            - int * Vec
        """
        # Variable to store another version of scalar-vector multiplication
        vector_product = []
        # Running a loop through all the elements in the vector
        for element in range(len(self.elements)):
            # Multiplying the each elements in the vector to the scalar value
            product_result = self.elements[element] * other
            # Appending the product of the elements to the list
            vector_product.append(product_result)
 
        # Converting the list to a vector
        vector_product = Vec(vector_product)
 
        return vector_product  # Returning the scalar-vector multiplication
 
    def __str__(self):
        """returns string representation of this Vec object"""
        return str(self.elements)  # does NOT need further implementation
    
    """Implementing norm(self, p) method"""
    # Writing a method that returns the Lp-norm of the vector
    def norm(self, p: int):
        # Storing the result of sum of powers
        sum_of_powers = 0
        # Iterating through each element in the vector
        for element in self.elements:
            # Adding the sum of the powers of each element
            sum_of_powers += abs(element) ** p # -> Summation of |x_i|^p
        # Sotring the final result
        lp_norm = sum_of_powers ** (1/p) # -> (Summation of |x_i|^p)^(1/p)
        # Returning the final result
        return lp_norm
            
            
# Putting up Matrix class from the previous assignment
class Matrix:
    
    def __init__(self, rowsp):  
        self.rowsp = rowsp
        self.colsp = self._construct_cols(rowsp)
 
    # Constructing columns based on the number of row space
    def _construct_cols(self, rowsp):
        # Intializing column space as an empty list
        colsp = []
        # Setting Column number the same as the number of rows in the row space
        cols_num = len(rowsp[0])
        # Creating a list of empty lists for each column space
        for _ in range(cols_num):
            colsp.append([])
        
        # Iterating through each row in the row space
        for row in rowsp:
            # Iterating through each entry in the row
            for i, entry in enumerate(row):
                # Appending the entry to the column space list
                colsp[i].append(entry)
        return colsp
 
    def set_col(self, j, u):
        '''
        Changes the j-th column to be the list `u`.  If `u` is not the same length 
        as the existing columns, then the method raises a `ValueError` with the 
        message `Incompatible column length.`
        '''
        # Conditional statement to check u = length of the existing columns
        if len(u) != len(self.colsp[0]):
            # Raising ValueError if condition is not met
            raise ValueError("Incompatible column length.")
        else: # Running the code below if the condition is met
            # Updating the first column space with the new column
            self.colsp[j - 1] = u # -> j-1 because the index starts from 0
            # Iterating through the row space
            for i in range(len(self.rowsp)):
                # Updating the row space with the new column
                self.rowsp[i][j - 1] = u[i]
 
    def set_row(self, i, v):
        '''
        Changes the i-th row to be the list `v`.  If `v` is not the same length 
        as the existing rows, then method raises a `ValueError` with the 
        message `Incompatible row length.`
        '''
        # Conditional statement to check v = length of the existing rows
        if len(v) != len(self.rowsp[0]): # Starting from 0 because the index starts from 0
            # Raising ValueError if condition is not met
            raise ValueError("Incompatible row length.")
        else: # Running the code below if the condition is met
            # Updating the row space with the new row
            self.rowsp[i - 1] = v
            # Reconstructing the column space of the matrix
            self.colsp = self._construct_cols(self.rowsp)
 
    def set_entry(self, i, j, x):
        '''
        Changes the existing a_ij entry in the matrix to 'x'.
        '''
        # Replacing the j-th entry in the row with x
        self.rowsp[i - 1][j - 1] = x # -> i-1, j-1 because the index starts from 0
        # Replacing the i-th entry in the column with x
        self.colsp[j - 1][i - 1] = x # -> i-1, j-1 because the index starts from 0
 
    # Returns the j-th column as a list
    def get_col(self, j):
        return self.colsp[j - 1] # -> j-1 because the index starts from 0
    
    # Returns the i-th row as a list v
    def get_row(self, i):
        return self.rowsp[i - 1] # -> i-1 because the index starts from 0
    
    # Returns the a_ij entry in the matrix
    def get_entry(self, i, j):
        return self.rowsp[i - 1][j - 1]
    
    # Returns the list of vectors that make up the column space of the matrix object
    def row_space(self):
        return self.rowsp
    
    # Returns the list of vectors that make up the row space of the matrix object
    def col_space(self):
        return self.colsp
    
    def get_diag(self, k):
        '''
        Returns the k-th diagonal of the matrix as a list, where:
        -> k = 0 returns the main diagonal
        -> k > 0 returns the diagonal beginning at a_1(k+1)
        -> k < 0 returns the diagonal beginning at a_-(k+1)1
        '''
        if k > 0:
            # Storing diagonal entries beginning at a_1(k+1)
            diag_3 = []
            # Iterating through the row spaces from a_1(k+1)
            for i in range(len(self.rowsp) - k):
                # Appending the values based on the given kth value
                diag_3.append(self.rowsp[i][i + k]) # -> 1(k+1) => (1)(k+1) => [i][i+k]
            # Returning the diagonal values from a_1(k+1)
            return diag_3
        elif k < 0:
            # Storing diagonal entries beginning at a_-(k+1)1 
            diag_2 = []
            # Iterating through the row spaces from a_-(k+1)1
            for i in range(len(self.rowsp) + k):
                # Appending the values based on the given kth value
                diag_2.append(self.rowsp[i - k][i]) # -> -(k+1)1 => (1-k)(1) => [i-k][i]
            # Returning the diagonal values from a_-(k+1)1
            return diag_2
        else:
            # Storing the main diagonal entries           
            main_diag = []
            # Iterating through the row spaces 
            for i in range(len(self.rowsp)):
                # Appending the values of the main diagonal
                main_diag.append(self.rowsp[i][i])
            # Returning the values of the main diagonal
            return main_diag
 
    def __add__(self, other):
        if len(self.rowsp) != len(other.rowsp) or len(self.colsp) != len(other.colsp):
            raise ValueError("Incompatible matrix dimensions for addition.")
        else:
            # Creating a list of empty lists for the sum of the matrices
            matrix_sum = []
            # Iterating through the row spaces
            for i in range(len(self.rowsp)):
                # Storing each reduced row in a list
                row_sum = []
                for j in range(len(self.colsp)):
                    # Appending the sum of the corresponding entries to row sum
                    row_sum.append(self.rowsp[i][j] + other.rowsp[i][j])
                # Appending the row sum to the matrix sum
                matrix_sum.append(row_sum)
            # Returning the matrix sum as a Matrix object
            return Matrix(matrix_sum)
 
    def __sub__(self, other):
        if len(self.rowsp) != len(other.rowsp) or len(self.colsp) != len(other.colsp):
            raise ValueError("Incompatible matrix dimensions for subtraction.")
        else:
            # Creating a list of empty lists for the difference of the matrices
            matrix_diff = []
            # Iterating through the row spaces
            for i in range(len(self.rowsp)):
                # Storing each reduced row in a list
                row_diff = []
                for j in range(len(self.colsp)):
                    # Appending the difference of the corresponding entries to row difference
                    row_diff.append(self.rowsp[i][j] - other.rowsp[i][j])
                # Appending the row difference to the matrix difference
                matrix_diff.append(row_diff)
            # Returning the reduced matrix as a Matrix object
            return Matrix(matrix_diff)
        
    def __mul__(self, other):  
        if type(other) == float or type(other) == int:
            # Storing the product of matrix-scalar multiplication
            scalar_mult_matrix = []
            # Iterating through each row in the row space
            for final_matrix_row in self.rowsp:
                # Storing the each scaled row in a list
                scaled_row = []
                # Going through each element in the row
                for element in final_matrix_row:
                    scaled_element = element * other # Mulitplying each element with the scalar value
                    scaled_row.append(scaled_element) # Appending the scaled product into the scaled row
                # Appending the scaled rows to the scaled matrix
                scalar_mult_matrix.append(scaled_row)
            return Matrix(scalar_mult_matrix) # Returning a scaled matrix as a Matrix object
        elif type(other) == Matrix: # --> If the other object is a matrix
            # Checking if dimensions of the matrices match or not
            if len(self.rowsp[0]) != len(other.rowsp):
                raise ValueError("Dimension mismatch for multiplication.")
            else: 
                # Array to store the product of the matrices
                product_of_matrices = []
                # Iterating through the rows of the first matrix
                for num in range(len(self.rowsp)):
                    # Storing the product of each row of the first matrix with the columns of the second matrix
                    final_matrix_row = []
                    # Iterating through the columns of the other matrix
                    for column in range(len(other.colsp)):
                        # Storing the sum of the product of each row 
                        matrix_sum = 0
                        # Iterating through the first index of the other matrix's column
                        for l in range(len(other.colsp[0])):
                            self_matrix_mul = self.rowsp[num][l] # Storing the multiplication of first matrix
                            other_matrix_mul = other.rowsp[l][column] # Storing the multiplication of the second matrix
                            matrix_sum += self_matrix_mul * other_matrix_mul # Adding the products of the two matrices' rows
                        # Appending the matrix sum to final matrix row
                        final_matrix_row.append(matrix_sum)
                    # Appending the final matrix rows to the final matrix product
                    product_of_matrices.append(final_matrix_row)
                return Matrix(product_of_matrices) # Returning the product of matrices as a Matrix object
        elif type(other) == Vec: # If the other object is a vector 
            # Storing the product of matrix-vector in a list
            matrix_vector_product = []
            # Iterating through the rows of the matrix
            for matrix_row in range(len(self.rowsp)):
                # Storing the sum of the product of each row
                mat_vec_product = 0
                # Iterating through each number in the matrix row
                for num in range(len(self.rowsp[matrix_row])):
                    # Adding the products of the matrix row and the vector
                    mat_vec_product += self.rowsp[matrix_row][num] * other.elements[num]
                matrix_vector_product.append(mat_vec_product) # Appending the matrix-vector product to the list
            return Vec(matrix_vector_product) # Returning the matrix-vector product as a Vec object
        else:
            print("ERROR: Unsupported Type.")
        return
    
    def __rmul__(self, other):  
        if type(other) == float or type(other) == int:
            return self.__mul__(other)
        else:
            print("ERROR: Unsupported Type.")
        return
    
    # Returns a formatted string representing the matrix entries as
    def __str__(self):
        """prints the rows and columns in matrix form """
        mat_str = ""
        for row in self.rowsp:
            mat_str += str(row) + "\n"
        return mat_str
                
    def __eq__(self, other):
        """overloads the == operator to return True if 
        two Matrix objects have the same row space and column space"""
        return self.row_space() == other.row_space() and self.col_space() == other.col_space()
 
    def __req__(self, other):
        """overloads the == operator to return True if 
        two Matrix objects have the same row space and column space"""
        return self.row_space() == other.row_space() and self.col_space() == other.col_space()
    
    """Implementing ref(self) method"""
    # Writing a method that returns the reduced row echelon form of the matrix
    def ref(self):
        # Creating a copy of the matrix 
        matrix_copy = []
        # Iterating through each row in the matrix
        for row in self.rowsp:
            # An temporary list to store the elements of the row
            new_row = []
            # Iterating through each element in the row
            for element in row:
                # Appending the element to the new row
                new_row.append(element)
            # Appending the new row to the matrix copy variable
            matrix_copy.append(new_row)
 
        # Storing the total number of rows and columns in the matrix
        num_rows = len(matrix_copy)
        num_cols = len(matrix_copy[0])
 
        # Making non-square matrices square by adding zero rows or columns as needed
        if num_rows != num_cols:
            # Checks if the number of rows < the number of columns
            if num_rows < num_cols:
                # Iterating through the number of columns - number of rows
                for i in range(num_cols, num_rows):
                    # Creating a zero row
                    zero_row = [0] * num_cols
                    # Appending the zero row to the matrix copy
                    matrix_copy.append(zero_row)
            else: # --> If the number of rows > the number of columns
                # Iterating through the number of rows - number of columns
                for i in range(num_cols, num_rows):
                    # Creating a zero column
                    zero_col = [0] * num_rows
                    # Iterating through the number of rows
                    for j in range(num_rows):
                        # Appending the zero column to the matrix copy
                        matrix_copy[j].append(zero_col[j])
 
        # Creating a variable to store the pivot column
        row_pivot = 0
 
        # Iterating through each column in the matrix
        for j in range(num_cols):
            # Finding the 1st non-zero entry in the j-th column below the pivot row
            for i in range(row_pivot, num_rows):
                # Checking if the entry is non-zero
                if matrix_copy[i][j] != 0:
                    # Swapping the rows if the entry is zero
                    matrix_copy[row_pivot], matrix_copy[i] = matrix_copy[i], matrix_copy[row_pivot]
                    break
            # Making of all the entries bwlow the pivot row zero
            for i in range(row_pivot + 1, num_rows):
                # Checking if the entry is non-zero
                if matrix_copy[i][j] != 0:
                    # Creating a variable to store the factor value
                    factor = matrix_copy[i][j] / matrix_copy[row_pivot][j]
                    # Iterating through each element in the row
                    # Alternative -> matrix_copy[i] = [matrix_copy[i][k] - scalar * matrix_copy[row_pivot][k] for k in range(num_cols)]
                    new_row = []
                    for k in range(num_cols):
                        new_element = matrix_copy[i][k] - (factor * matrix_copy[row_pivot][k])
                        new_row.append(new_element)
                    # Replacing the row with the new row
                    matrix_copy[i] = new_row
            # Moving to the next pivot row
            row_pivot += 1
            # Checking if the pivot row is the last row
            if row_pivot == num_rows:
                break
        # Returning the reduced row echelon form of a matrix
        return Matrix(matrix_copy)        
 
    """Implementing rank(self) method"""
    # Writing the method that returns the rank of the matrix
    def rank(self):
        # Converting input Matrix into reduced row echelon form
        ref_matrix = self.ref()
        # Creating a variable to store the rank of the matrix
        rank = 0
        # Storing total number of non-zero rows and columns in the matrix
        non_zero_rows = 0
        non_zero_cols = 0
        # Writing non_zero_rows = sum([any(row) for row in ref_matrix.rowsp]) in a different way
        # Iterating through each row in the matrix
        for row in ref_matrix.rowsp:
            # Checking if the row has any non-zero entries
            if any(row):
                # Incrementing the non_zero_rows variable
                non_zero_rows += 1
        # Writing non_zero_cols = sum([any(col) for col in ref_matrix.colsp]) in a different way
        # Iterating through each column in the matrix
        for col in ref_matrix.colsp:
            # Checking if the column has any non-zero entries
            if any(col):
                # Incrementing the non_zero_cols variable
                non_zero_cols += 1
        
        # Checking if the number of non-zero rows > the number of non-zero columns
        if non_zero_rows < non_zero_cols:
            rank = non_zero_rows
        elif non_zero_rows > non_zero_cols: # --> If the number of non-zero rows > the number of non-zero columns
            rank = non_zero_cols
        else:
            rank = non_zero_rows
        
        # Returning the rank of the matrix
        return rank
'''
m = Matrix([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
n = Matrix([[1, 3, 5, 9], [1, 3, 1, 7], [4, 3, 9, 7], [5, 2, 0, 9]])
o = Matrix([[1, 2], [3, 4]])
p = Matrix([[-24, 60, 56, -28, 24, 80], [-6, 15, 14, -7, 6, 20], [-36, 20, 24, 36, -8, -34], [-16, 9, -5, -2, -9, 9], [-18, 10, 12, 18, -4, -17]])
q = Matrix([[13, -8, -13, 1, -19, 1, 7], [11, 6, -109, 122, 26, 125, -3], [11, 17, 10, -9, -9, -6, -11], [11, -1, 18, -18, -9, -8, 18], [16, 7, 6, 7, 15, -4, 19], [0, -1, 13, -20, -5, -19, 3], [14, -7, -15, -10, 6, -18, 13]])

print(m.ref())
# Output: [[1, 2, 3], [0, -3, -6], [0, 0, 0]]
print(n.ref())
# Output: [[1, 3, 5, 9], [0, -9, -11, -29], [0, 0, -4, -2], [0, 0, 0, 94/9]]
print(o.ref())
# Output: [[1, 2], [0, -2]]
print(p.ref())
# Output: [[1, 0, 0, 0, 0.638066, -1.64437], [0, 1, 0, 0, 0.3287, -1.74054], [0, 0, 1, 0, 0.3498, 1.33333], [0, 0, 0, 1, 0, -2.510744], [0, 0, 0, 0, 0, 0]]
print(q.ref())
'''
"""RANK TESTER CELL
A = Matrix([[0, 1, 2], [3, 4, 5], [6, 7, 8]])
print(A)
print("Rank:", A.rank(), "\nExpected: 2\n")

B = Matrix([[1, 2], [-1, -2]])
print(B)
print("Rank:", B.rank(), "\nExpected: 1\n")

C = Matrix([[0, -1, 5], [2, 4, -6], [1, 1, 5]])
print(C)
print("Rank:", C.rank(), "\nExpected: 3\n")

D = Matrix([[5, 3, 0], [1, 2, -4], [-2, -4, 8]])
print(D)
print("Rank:", D.rank(), "\nExpected: 2\n")

E = Matrix([[1, 2, -1, 3], [2, 4, 1, -2], [3, 6, 3, -7]])
print(E)
print("Rank:", E.rank(), "\nExpected: 2")
"""
Problem 2
Implement the function gauss_solve(A, b) that solves the system  Ax→=b→
 . The input A is of the type Matrix and b is of the type Vec.

If the system has a unique solution, it returns the solution as a Vec object.
If the system has no solution, it returns None.
If the system has infinitely many solutions, it returns the number of free variables (int) in the solution.
# Writing the gauss_solve(A, b) function to solve the system of linear equations
def gauss_solve(A, b):
    # TODO: Constructing a new matrix by appending the b vector to the A matrix
    aug_matrix = []
    # Converting the augmented matrix into a Matrix object
    aug_matrix = Matrix(aug_matrix)
    # Converting the augmented matrix into reduced row echelon form
    ref_aug_matrix = aug_matrix.ref()
    # Storing the number of columns of the reduced, augmented matrix
    aug_mat_cols = len(ref_aug_matrix.col_space())

    # Checking if the system of equations has no, one or infinite solutions
    if A.rank() < ref_aug_matrix.rank():
        return None
    elif A.rank() == ref_aug_matrix.rank() == aug_mat_cols:
        result = []
        # TODO: Using back substitution to solve the system of equations
        return Vec(result)
    elif A.rank() < aug_mat_cols and ref_aug_matrix.rank() < aug_mat_cols:
        free_variables = aug_mat_cols - A.rank()
        return free_variables
"""TESTER CELL #1 FOR GAUSSIAN ELIMINATION"""
A = Matrix([[0, 1, 2], [3, 4, 5], [6, 7, 8]])
b = Vec([9, 10, 11])
sol = gauss_solve(A, b)
print("Result:", sol)
print("Expected: 1")
"""TESTER CELL #2 FOR GAUSSIAN ELIMINATION
A = Matrix([[1, 0, 5], [0, 1, 2], [3, 2, 0]])
b = Vec([6, 3, 5])
sol = gauss_solve(A, b)
print("Returned:", sol)
print("Expected: [1.0, 1.0, 1.0]")
"""
Returned: None
Expected: [1.0, 1.0, 1.0]
"""TESTER CELL #3 FOR GAUSSIAN ELIMINATION
A = Matrix([[1, 1, 5], [2, 2, 10]])
b = Vec([6, 3])
sol = gauss_solve(A, b)
print("Returned:", sol)
print("Expected: None")
"""
Problem 3
Implement the function is_independent(S) that returns True if the set S of Vec objects is linearly independent, otherwise returns False.

# Writing a function that returns true/false based on whether 
# the given set of vectors is linearly independent or not
def is_independent(S):
    # Two arrays for storing the matrix and vector
    A = []
    B = []
    # Iterating through the vector space
    for x in S:
        # Storing the elements of the matrix
        A_new = []
        # Iterating through the elements of the vector
        for y in range(len(x.elements)):
            # Appending the elements of the vector to the matrix
            A_new.append(x.elements[y])
        # Appending the elements of the vector to the matrix
        B.append(0)
        # Appending the matrix to the list
        A.append(A_new)

    # Converting the matrix and vector into Matrix and Vec objects
    A_matrix = Matrix(A)
    B_vector = Vec(B)

    # Running the gauss_solve() function to solve the system of linear equations
    gauss_solution = gauss_solve(A_matrix, B_vector)

    # Checking if the system of linear equations has no solution
    if type(gauss_solution) == Vec:
        # Iterating through the elements of the vector
        for i in gauss_solution.elements:
            # Checking if the element is not zero
            if i != 0:
                break
            # Returning true, indicating that the vectors are linearly independent
            return True
    # Returning false, indicating that the vectors are linearly dependent
    return False
"""IS-INDEPENDENT TESTER CELL

S1 = {Vec([1, 2]), Vec([2, 3]), Vec([3, 4])}

print("S1 is Independent:", is_independent(S1))
print("Expected: False")

S2 = {Vec([1, 1, 1]), Vec([1, 2, 3]), Vec([1, 3, 6])}

print("S2 is Independent:", is_independent(S2))
print("Expected: True")
"""
Problem 4
Implement the function gram_schmidt(S) that applies the Gram-Schmidt process to create an orthonormal set of vectors from the vectors in S. The function raises a ValueError if the set S is NOT linearly independent.

INPUT:

S a set of Vec objects
OUTPUT:

a set of Vec objects representing orthonormal vectors.
HINT:

If  S={x1→,x2→,…,xn−→}
  is a set of linearly independent vectors, then Gram-Schmidt process returns the set  {u1→,u2→,…,un−→}
  where,

ui→=1||wi−→||2wi−→
  for  i=1,2,…n
 ,
and

w1−→=x1→
 
wi−→=xi→−∑i−1j=1projwj−→(xi→)
  for  i=2,3,…n
 
# Writing a function that returns the orthonormal set of vectors in S
def gram_schmidt(S):
    if is_independent(S) == False:
        raise ValueError("The vectors in S are not linearly independent.")
    else:
        None
    pass
"""TESTER CELL #1 FOR GRAM SCHMIDT
S = {Vec(1, -1), Vec(0, 2)}
T = gram_schmidt(S)

str_T = "{"
for v in T:
    str_T += str(v) + 'T '
str_T += "}"

print(strT)
print("Expected: {[0.707106, -0.707106]T, [0.707106, 0.707106]T}")
"""
"""TESTER CELL #2 FOR GRAM SCHMIDT
S = {Vec(1, -2), Vec(-4, 8)}
try:
    T = gram_schmidt(S)
    print("INCORRECT: ValueError was not raised.")
except ValueError:
    print("CORRECT: ValueError was raised.")
except:
    error = traceback.format_exc()
    print("INCORRECT: The following unexpected error occurred:\n\n" + str(error))
"""