26.3: Gram-Schmidt Orthogonalization Process

import math
import copy
from urllib.request import urlretrieve
urlretrieve('https://raw.githubusercontent.com/colbrydi/jupytercheck/master/answercheck.py', 
            'answercheck.py');

def transpose(A):
    '''Calculate the transpose of matrix A represented as list of lists'''
    n = len(A)
    m = len(A[0])
    AT = list()
    for j in range(0,m):    
        temp = list()
        for i in range(0,n):
            temp.append(A[i][j])
        AT.append(temp)
    return AT

Do This

Implement the Gram-Schmidt orthoganalization process from the Hefron textbook (page 282). This function takes a \(m \times n\) Matrix \(A\) with linearly independent columns as input and return a \(m \times n\) Matrix \(G\) with orthogonal column vectors. The basic algorithm works as follows:

• AT = transpose(A) (this process works with the columns of the matrix so it is easier to work with the transpose. Think about a list of list, it is easy to get a row (a list)).
• Make a new empty list of the same size as AT and call it GT (G transpose)
• Loop index i over all of the rows in AT (i.e. columns of A)
  • GT[i] = AT[i]
  • Loop index j from 0 to i
    • GT[i] -= proj(GT[i], GT[j])
• G = transpose(GT)

Use the following function definition as a template:

def GramSchmidt(A):
    return G

Here, we are going to test your function using the vectors:

A4 = [[1,4,8],[2,0,1],[0,5,5],[3,8,6]]
print(transpose(A4))
G4 = GramSchmidt(A4)
print(transpose(G4))

from answercheck import checkanswer

checkanswer.matrix(G4,'a472a81eef411c0df03ae9a072dfa040');

A2 = [[-4,-6],[3,5]]
print(transpose(A2))
G2 = GramSchmidt(A2)
print(transpose(G2))

from answercheck import checkanswer

checkanswer.matrix(G2,'23b9860b72dbe5b84d7c598c08af9688');

Question

What is the Big-O complexity of the Gram-Schmidt process?