Subsection 4.4.1 AlgoMatrix basics
We would like to consider two different methods of initializing an AlgoMatrix. The default is to allow any rectangular grid of complex numbers, but to encourage the idea that a matrix \(A \in \Mats{m,n}\) can be represented \(A=\left[\vec{A}_0 | \vec{A}_1 | \cdots | \vec{A}_{n-1} \right]\) , where \(\entry{A}{r,c} = \entry{\vec{A}_c}{r}\) for appropriate \(r\) and \(c\text{,}\) we will also permit a list of vectors all of the same length.
Activity 4.6. AlgoMatrix initialization.
In order to develop the __init__(self, grid) method, we have to validate the input. We will allow the initialization to fail naturally if we attempt to index into grid and it is not an indexable object.
(a) Setting up your files.
The main class file should be AlgoMatrix.py with an appropriate header followed by from AlgoVector import *. The testing and worknig file should be aam_proj5.py with an appropriate header. Further, the initializtion method should begin as follows:
class AlgoMatrix:
def __init__(self, grid):
'''Initialize an AlgoMatrix from 'grid', which is either a list
of list (or tuple or tuple or some combination thereof) of
complex values, or a list (or tuple) of AlgoVector objects.'''
try:
if type(grid[0]) == AlgoVector:
# This will get filled in during the next task
else:
# This will get filled in during the next after that
# Then we have to write the exception handler, because without an
# 'except:' block this will cause a SyntaxError
(b) A list of AlgoVector objects.
Inside the first step of the validation, the important things to check are to determine whether remaining elements of grid are actually AlgoVector objects and also to determine that all have the same length. Correct the above code with the following, making modifications as necessary:
if type(grid[0]) == AlgoVector:
n = len(grid)
# The next line works as long as AlgoVector has a __len__ method!
m = len(grid[0])
new_grid = [ ]
for x in grid[0].entries():
new_grid.append( [x] )
for vec in grid[1:]:
if type(vec) != AlgoVector:
raise TypeError('Malformed list of AlgoVector objects')
elif len(vec) != m:
raise ValueError('Malformed list of AlgoVector objects')
else:
for r in range(m):
# Now you have to fill in: we want to add the rth entry of
# the current vector, vec, to the rth row of new_grid.
continue
else:
# This will get filled in during the next task
(c) A list of lists of complex-compatible objects.
This execution path proceeds slightly more smoothly, as the input is not of a form which is trying to specify a matrix in the transpose order of columns before rows. Complete the following:
else:
m = len(grid)
n = len(grid[0])
new_grid = [ ]
for r in range(m):
if len(grid[r]) != n:
raise ValueError('Malformed grid of complex numbers')
new_grid.append( [ ] )
for c in range(n):
# What do we want to actually append into our new rows?
# The next line inserts dummy values of 0 in all positions
new_grid[-1].append( complex( 0 ) )
(d) Handling exceptions.
As it turns out, we actually want to stop the execution of the program if any of the generated exceptions come up. This is handled by simply putting the command raise in the except:... block without any argument. This causes the exception which brought about the problem to be passed up to the next level; this could be a try:... except:... block in a calling function, or it could be the main execution loop of Python. In the latter case, this causes an error and stops execution of your code!
Of course, you also have to store the important data attributes outside the exception handler, since the assignment of attributes is the final step of creating a usable class object.
except:
raise
self._data = tuple(tuple(row) for row in new_grid)
self._row_dim = len(new_grid)
self._col_dim = len(new_grid[0])
(e) Representation.
Representing the object is next. Return the str version of self._data instead of "None" in the below code.
def __repr__(self):
return "None"
(f) Test your work up to this point!
At this point you have a substantial amount of code, although you are not finished. Test your work in aam_proj5.py by creating the following matrices and vectors:
\begin{align*}
A \amp= \begin{bmatrix}
1 \amp 2 \amp 3 \\
-2 \amp 1 \amp -3 \\
-3 \amp 2 \amp -1
\end{bmatrix} \amp
\vec{b}_1 \amp= \cvec{3+4j\\5+12j\\7+24j} \amp
\vec{b}_2 \amp= \cvec{1-\frac12 j\\2-\frac13 j \\ 3-\frac14 j} \amp
B \amp= [\vec{b}_1|\vec{b}_2]\text{.}
\end{align*}
Explicitly print the representation of these matrices using print(repr(a_matrix)), where a_matrix is replaced by the variable names you choose for \(A\) and \(B\text{.}\)
Before we get to operations involving multiple objects, we want to set up bracket notation for matrices. Just as we use \(\entry{A}{r,c}\) to represent the entry in the rth-indexed row and cth-indexed column of a matrix \(A\in\Mats{m,n}\text{,}\) we want to use the_mat[r,c] to represent the same object for an AlgoMatrix called the_mat. We implement this using __getitem__ but we have to be slightly careful about the arguments to the method.
Activity 4.7. Matrix entries and testing equality.
(a) Matrix dimension.
Since a dims function is necessary in order to check that the input to __getitem__ falls within the range of valid indices, as well as to check matrix equality, we first define a dims(self) method.
def dims(self):
'''Return the (row,column) dimensions of self.'''
return (self._row_dim, self._col_dim)
(b) Fetching from an index.
The only care necessary is to make sure that the pair of indices is passed as a single variable. Implement the following.
def __getitem__(self, index_pair):
'''if r,c == index_pair, return self[r,c]'''
r,c = index_pair
m,n = self.dims()
if r not in range(m) or c not in range(n):
raise IndexError('No such entry.')
else:
# What needs to be returned?
(c) Well-formatted output.
While the __repr__ method is sufficient for a class file, it will be difficult to see whether or not your matrices are correct in tuple-of-tuples form. Implement this __str__ method.
def __str__(self):
"""Return a human-readable matrix of self"""
# This is highly condensed code. Copy it exactly and change nothing.
try:
return self._nice_str
except AttributeError:
m,n = self.dims()
str_mat = [[str(self[r,c]).replace('(','').replace(')','') for c in
range(n)] for r in range(m)]
clen = [max( len(str_mat[r][c]) for r in range(m) ) for c in range(n)]
str_mat = [[("{s:>%d}"%clen[c]).format(s=str_mat[r][c]) for c in range(n)]
for r in range(m)]
str_mat = [("[ "+', '.join(row) + " ]") for row in str_mat]
str_mat = "[" + "\n ".join(str_mat) + "]"
self._nice_str = str_mat
return str_mat
(d) Testing matrix equality.
Three things need to be tested when executing __eq__(self, right): firstly, the argument right must be of type AlgoMatrix; secondly, the dimensions of self and right must agree; thirdly, the values in each entry of self and of right must agree. Good thing we defined __getitem__! Implement the following, determining whether each of bool_1, bool_2, and bool_3 needs to be True or False.
if type(self) != type(right) or self.dims() != right.dims():
return bool_1
else:
m,n = self.dims()
for r in range(m):
for c in range(n):
if self[r,c] != right[r,c]:
return bool_2
return bool_3
(e) Testing your work.
In your aam_proj5.py file, print the matrices \(A\) and \(B\) you defined previously, this time just using the print(...) command as normal. Also find the dimensions using your program, and check to see if \(A=B\text{.}\)
Since we have included our AlgoVector class from the beginning, it makes sense to analyze matrix multiplication in three distinct forms: two forms where the matrix is the multiplier (left factor) and one where it is the multiplicand (right factor).
Activity 4.8. Multiplication in AlgoMatrix.
The two forms of multiplication with a matrix as the multiplier are matrix-vector multiplication and matrix-matrix multiplication. In each case, there is a consideration as to the size of the multiplicand as compared to the size of the multiplier, and those sizes will need to be checked during input validation. The only other valid multiplication case occurs when a non-matrix is the multiplier and the matrix is the multiplicand, which only occurs during scalar multiplication; therefore in that case the only constraint is to check that the scalar is in fact a complex number.
(a) AlgoMatrix as multiplier: __mul__.
Begin with the following:
def __mul__(self, right):
'''Return self*right, which necessitates that right be an AlgoVector
or another AlgoMatrix.'''
if type(right) == type(self):
# This is matrix-matrix multiplication
pass
elif type(right) == AlgoVector:
# This is matrix-vector multiplication
pass
else:
raise TypeError(f'Cannot multiply AlgoMatrix*{type(right)}')
(i) Matrix-matrix multiplication.
While it is best to define matrix-matrix multiplication as iterated matrix-vector multiplication, that is not the optimal way to implement the product. Instead, it’s best to check the dimensions of the two matrices and proceed to build the product of \(A\) and \(B\) by using \(\entry{AB}{r,c} = \sum_{k=0}^{n-1}\entry{A}{r,k}\entry{B}{k,c}\) when \(A\in\Mats{m,n}\) and \(B\in\Mats{n,q}\text{.}\)
if type(right) == type(self):
# This is matrix-matrix multiplication
m,n = self.dims()
p,q = right.dims()
# What condition needs to be checked on this line to ensure
# dimensions are correct? Change CONDITION on the following line.
if CONDITION:
new_grid = [ ]
# How many rows has the product matrix?
for r in range( number_of_rows ):
new_grid.append( [ ] )
# How many columns has the product matrix?
for c in range( number_of_columns ):
total = 0
# How many terms must be summed?
for k in range( number_of_terms ):
total += self[r,k] * right[k,c]
new_grid[-1].append(total)
return AlgoMatrix(new_grid)
else:
raise ValueError("Dimension mismatch")
Note that as usual there are several places where that code must be modified to work correctly.
(ii) Matrix-vector multiplication.
Recall that according to its definition, a matrix-vector product is a linear combination of vectors. Once again the best way to define the product is not the most efficient way to compute it; we instead use the component-wise approach to build the result as a list using \(\entry{A\vv}{r} = \sum_{c=0}^{n-1} \entry{A}{r,c}\entry{\vv}{c}\) where \(A\in\Mats{m,n}\) and \(\vv\in\CV{n}\text{.}\)
elif type(right) == AlgoVector:
# This is matrix-vector multiplication
m,n = self.dims()
if len(right) == n:
# The dimensions of the vector and matrix are compatible
new_list = [ ]
for c in range(n):
new_list.append( SOMETHING )
else:
raise ValueError("Dimension mismatch")
(b) AlgoMatrix as multiplicand.
Unlike vectors, since matrix-matrix multiplication exists there is a use case for matrices being the multiplicand. However that particular use case is handled in Python (via order of operations) by left multiplication and __mul__. Therefore all we need to implement in the __rmul__ method is scalar-matrix multiplication, which operates the same way in AlgoMatrix as in AlgoVector, extended to handle both rows and columns.
def __rmul__(self, left):
try:
scalar = complex(left)
except:
raise TypeError(f"Invalid scalar {left} for AlgoMatrix multiplication")
new_grid = [ ]
m,n = self.dims()
for r in range(m):
new_grid.append( [ ] )
for c in range(n):
#
# What has to go in the inner lists?
# Append that to new_grid[-1]
#
continue
return AlgoMatrix(new_grid)
(c) Test your work up to this point!
Now define a new AlgoMatrix in your aam_proj5.py file, representing the matrix
\begin{equation*}
I_3 = \begin{bmatrix}
1 \amp 0 \amp 0\\
0 \amp 1 \amp 0\\
0 \amp 0 \amp 1
\end{bmatrix}
\end{equation*}
and test your multiplication code to see if \(1A\) and \(I_3A\) are equal.
Compared to multiplication, addition inside \(\Mats{m,n}\) is a breeze.
Activity 4.9. Addition in AlgoMatrix.
Implementation of addition follows the pattern in AlgoMatrix that was established in AlgoVector: raise an error for __radd__ and do the straightforward computation in __add__. Since other types natively do not add with AlgoMatrix we can safely let the failure to allow an AlgoMatrix to be a right-summand to fall onto the left addition of the other class.
def __add__(self, right):
'''Return self+right'''
# validate type of right
if TEST_CONDITION1:
# Compare dimensions
m,n = self.dims()
p,q = right.dims()
if TEST_CONDITION2:
new_grid = [ ]
for r in range(m):
new_grid.append( [ ] )
for c in range(n):
#
# What has to go in the inner lists?
# Append that to new_grid[-1]
# Remember: we implemented bracket notation!
#
continue
return AlgoMatrix(new_grid)
else:
raise ValueError("Dimension mismatch")
else:
raise TypeError(f"Cannot add AlgoMatrix and {type(right)}")
Test this in your aam_proj5.py file by checking to see that \(A+A = 2A\text{.}\)
Subsection 4.4.2 Named AlgoMatrix methods
In addition to the AlgoMatrix.dims() method we defined above, we should create some other named methods.
Activity 4.10. AlgoMatrix as column matrices.
The notation \(A=\left[\vec{A}_0 | \vec{A}_1 | \cdots | \vec{A}_{n-1}\right]\) for a matrix \(A\in\Mats{m,n}\) is sometimes called augmented notation. Regardless of what the notation is called, its use implies that we sometimes wish to isolate a particular column vector of a matrix, or consider the list of all column vectors.
(a) Isolating a single column vector.
First we write a method which produces a particular indexed column vector.
def column(self, col_index):
"""Return the column vector of self in the given column index."""
if col_index not in range(self._col_dim):
raise IndexError(f'Bad column index {col_index}.')
else:
new_list = [ ]
for r in range(self._row_dim):
#
# Here we only want a list, not a grid; what must
# be in the rth row of the output vector?
#
continue
return AlgoVector(new_list)
(b) Creating the tuple of all column vectors.
We can leverage the just-written AlgoMatrix.column(col_index) method to create a method which returns a tuple of all the column vectors of a matrix.
def columns(self):
'''Return a tuple of all column vectors of self'''
new_list = [ ]
#
# Write this yourself!
#
return tuple(new_list)
(c) Test your work up to this point!
Once again, what we already have used in aam_proj5.py can be utilized to test if your code is working. Try the following, replacing the variable name B with the name of your matrix \(B\text{.}\)
print(AlgoMatrix(B.columns()) == B)
Now move on to implementing conjugation, where \(\entry{\conj{A}}{r,c} = \conj{\entry{A}{r,c}}\text{.}\)
Activity 4.11. Complex conjugate of an AlgoMatrix.
This activity is no more complicated than it was for vectors, except in the use of the nested loop structure.
def conjugate(self):
'''Return the complex conjugate of self.'''
new_grid = [ ]
for r in range(self._row_dim):
new_grid.append( [ ] )
for c in range(self._col_dim):
#
# What do we append to new_grid[-1] this time?
#
continue
return AlgoMatrix(new_grid)
Test this in aam_proj5.py by printing \(\conj{A}\text{.}\)
As a sort of reverse procedure of the column and columns methods defined above, we define augmentation of a matrix.: given a matrix \(A\in\Mats{m,n}\) and a vector \(\vv\in\CV{m}\text{,}\) you can augment \(A\) by \(\vv\text{,}\) resulting in a matrix \(\left[A | \vv\right]\) with columns in indices 0 through \(n-1\) exactly the columns of \(A\) but with the vector \(\vv\) as a column of index \(n\text{.}\) Moreover, given a matrix \(B\in\Mats{m,q}\text{,}\) the similarly-defined matrix \(\left[A|B\right]\) has columns with indices 0 through \(n-1\) equal to the corresponding column of \(A\text{,}\) but additionally another \(q\) columns, where the column indexed \(n+c\) is the column of \(B\) with index \(c\text{.}\)
Definition 4.4.1. Augmented matrices.
Let \(m,n,q\in\Zp\) be given, and suppose \(A\in\Mats{m,n}\text{,}\) \(B\in\Mats{m,q}\text{,}\) and \(\vv\in\CV{m}\text{.}\) Then we can define the matrix \(A\) augmented by \(B\) to be the matrix \([A|B]\in\Mats{m,n+q}\text{.}\) While proper use of notation dictates that the entries should be \(\entry{[A|B]}{r,c}\text{,}\) we suppress the inner brackets and allow that \([A|B]\) is the unique matrix satisfying
\begin{equation*}
\entry{A|B}{r,c} = \begin{cases}
\entry{A}{r,c} \amp c\in\set{0,1,\dotsc,n-1} \\
\entry{B}{r,c-n} \amp c\in\set{n,n+1,\dotsc,n+(q-1)}
\end{cases}\text{.}
\end{equation*}
Similarly, \([A|\vv]\in\Mats{m,n+1}\) is the matrix \(A\) augmented by \(\vv\text{,}\) satisfying
\begin{equation*}
\entry{A|\vv}{r,c} = \begin{cases}
\entry{A}{r,c} \amp c\in\set{0,1,\dotsc,n-1} \\
\entry{vv}{r} \amp c=n
\end{cases}
\end{equation*}
Example 4.4.2. Some augmented matrices.
Consider the following matrices and vector:
\begin{align*}
A \amp= \begin{bmatrix}
1+1j \amp 1-2j \amp 1-3j \\
-1+2j \amp 2+2j \amp 1-4j \\
-1+3j \amp -1+4j \amp 3+3j
\end{bmatrix} \amp
B \amp= \begin{bmatrix}
1 \amp \frac12 \amp \frac13 \\
\frac12 \amp \frac13 \amp \frac14 \\
\frac13 \amp \frac14 \amp \frac15
\end{bmatrix} \amp
\vv \amp= \cvec{1+j\\1+\sqrt{2}j\\1+\sqrt{3}j}
\end{align*}
Then by augmentation we have the matrices \([A|B]\) and \([A|\vv]\) given by
\begin{align*}
[A|B] \amp= \begin{bmatrix}
1+1j \amp 1-2j \amp 1-3j \amp 1 \amp \frac12 \amp \frac13 \\
-1+2j \amp 2+2j \amp 1-4j \amp \frac12 \amp \frac13 \amp \frac14 \\
-1+3j \amp -1+4j \amp 3+3j \amp \frac13 \amp \frac14 \amp \frac15
\end{bmatrix}\\
[A|\vv] \amp= \begin{bmatrix}
1+1j \amp 1-2j \amp 1-3j \amp 1+1j\\
-1+2j \amp 2+2j \amp 1-4j \amp 1+\sqrt{2}j\\
-1+3j \amp -1+4j \amp 3+3j \amp 1+\sqrt{3}j
\end{bmatrix}\text{.}
\end{align*}
Activity 4.12. AlgoMatrix augmentation.
We should easily see how to use our special definition of initialization by lists of column vectors to perform augmentation. In fact, augmentation is the reason why that option for initialization is a good idea!
def augment(self, right):
'''Return the augmented matrix [self|right]'''
m,n = self.dims()
if type(right) == AlgoVector:
if len(right)==m:
return AlgoMatrix( self.columns() + tuple([right]) )
else:
raise ValueError('Dimension mismatch')
elif type(right) == AlgoMatrix:
p,q = right.dims()
if p==m:
return AlgoMatrix( self.columns() + right.columns() )
else:
raise ValueError('Dimension mismatch')
else:
raise TypeError(f'Cannot augment AlgoMatrix by {type(right)}.')
In aam_proj5.py, test this by printing the matrices \([A|B]\) and \([B|A]\text{;}\) are they equal?
Now for something completely different! We discussed that every matrix \(A\in\Mats{m,n}\) is associated with a linear transformation \(T_A:\CV{n}\to\CV{m}\) defined by \(T_A(\vv) = A\vv\) for every \(\vv\in\CV{n}\text{.}\) We did not discuss the existence of the matrix transpose, which provides a function with domain \(\CV{m}\) and codomain \(\CV{n}\) which is related to \(T_A\) but is generally not \(T_A^{-1}\text{,}\) an amazing but interesting fact!
Definition 4.4.3. Transpose of a matrix.
Suppose that \(A\in\Mats{m,n}\text{.}\) Then there is a unique matrix called the transpose of \(A\text{,}\) denoted \(A^T\in\Mats{n,m}\text{,}\) satisfying
\begin{equation*}
\entry{A^T}{c,r} = \entry{A}{r,c}
\end{equation*}
for all \({r\in\set{0,1,\dotsc,m-1}}\) and \({c\in\set{0,1,\dotsc,n-1}}\text{.}\)
Further, the linear transformation associated with \(A^T\) is necessarily \(T_{A^T}:\CV{m}\to\CV{n}\) given by \(T_{A^T}(\vv) = A^T\vv\) for any \(\vv\in\CV{m}\text{.}\)
The relationship between the dimensions of \(A\) and \(A^T\) ensure the following theorem.
Theorem 4.4.4. Certain matrix products always exist.
Suppose that \(A\in\Mats{m,n}\text{,}\) so that \(A^T\in\Mats{n,m}\text{.}\) Then both \(A^TA\) and \(AA^T\) exist, with \(A^TA\in\Mats{n,n}\) and \(AA^T\in\Mats{m,m}\text{.}\)
Activity 4.13. Transpose of an AlgoMatrix.
The definition in terms of entries using bracket notation makes the transpose mostly simple to define; care needs to be taken to make sure the dimension is correct.
def transpose(self):
'''Return the matrix transpose of self.'''
new_grid = [ ]
for c in range(self._col_dim):
new_grid.append( [ ] )
for r in range(self._row_dim):
#
# Do not be fooled! Append the correct entry of self
# in this position to new_grid[-1]
#
continue
return AlgoMatrix(new_grid)
To test this, calculate the following in aam_proj5.py:
\begin{equation*}
A^T, B^T, (AB)^T, B^TA^T
\end{equation*}
and then draw a conclusion about the relationship between \(A^T\text{,}\) \(B^T\text{,}\) and \((AB)^T\text{.}\)
