Contents |

Matrices, commonly used in mathematics, are easily represented by two-dimensional
arrays in Python. A two-dimensional array is an array whose elements are arrays
themselves^{50}.
Matrices, like tables (the ones that contain data, not the dining room kind), can be divided
into rows and columns. A matrix with *p* rows and *q* columns is said to
be an *p x q* matrix.
First, we delve into creating matrices and then we will study using them to
solve some problems.

To make
a 3x3 matrix *m*, one starts by making an array that is 3 elements
long. One could simply specify the array directly:

m = [None,None,None] #attempt 1

Note we have initialized the array so that each slot in the array holds the value
`None`

. This approach works fine if the size of the array is small and known in
advance. In other cases, we can use a Python trick to quickly construct an array
of a given size:

m = [None] * 3 #attempt 2

We have hardwired the 3 in the above code fragment, but we could use a variable instead, unlike the first attempt. In fact, we use this trick to define a general-purpose function that makes an array of a given size:

def createArray(size): return [None] * size m = createArray(3) # attempt 3

We designate this initial array as the *backbone* of the matrix.
Pictorially, *m* looks like this:

The next step is to assign each slot in the backbone to point to an array of size 3:

m = createArray(3) #attempt 4 m[0] = createArray(3) m[1] = createArray(3) m[2] = createArray(3)

Now *m* looks like this:

Of course, creating the matrix this way requires we know the size in advance. If we do not, we can use a loop to set the slots of the backbone:

size = 3 m = createArray(size) #attempt 5 for i in range(0,size,1): m[i] = createArray(size)

This code works great if the matrix is *square* (i.e. the number of rows equals the number of
columns). If not, we replace size in the code above with explicit values for the
number of rows and the number of columns:

rows = 3 cols = 4 m = createArray(rows) #attempt 6 for i in range(0,rows,1): m[i] = createArray(cols)

We can see from this code that the length of the backbone corresponds to the number of rows
while the length of the arrays to which the backbone slots point represents the number of
columns^{51}.
Wrapping this code in function that creates a matrix with a given number of rows and
columns yields:

def createMatrix(rows,cols): m = createArray(rows) for i in range(rows): m[i] = createArray(cols) return m

To retrieve a value at row *r* and column *c* from a matrix *m*,
one uses an expression similar to:

value = m[r][c]

One
can set the value of the element at row *r* and column *c*
with an expression similar to:

m[r][c] = value

Because matrices are built from arrays, the first row has index 0
and the first column has index 0 as well. Thus the first value
in the
first row in matrix *m* can be found at:

m[0][0]

Where is the last element in the last row found in a matrix *m* with
*x* rows and *y* columns?
Highlight the following line to see the answers:

[ m[x-1][y-1] ]

Matrices are typically processed with with two nested *for* loops. The outer loop
runs over the rows, while the inner loop runs over the columns of each row. Here is
a generic function for working with a matrix:

def processMatrix(m): rows = len(m) cols = len(m[0]) for r in range(0,rows,1): for c in range(0,cols,1): # do something with m[r][c] return

Note how we retrieve the number of rows by determining the length of the backbone and the number of columns be determining the length of one of the rows.

One useful thing to do with a matrix is visualize it. In other words, we might
wish to print out its contents.
Using the general purpose template *processMatrix*
as a guide, we simply substitute a print statement for the processing
comment:

def displayMatrix(m): rows = len(m) cols = len(m[0]) for r in range(0,rows,1): for c in range(0,cols,1): print(m[r][c]) return

If we were to print this matrix:

1 | 2 | 3 |

4 | 5 | 6 |

we would see this output:

1 2 3 4 5 6

The good news is we printed every element as desired. The bad news is our
output looks nothing like a matrix; every element is printed on a line
by itself. We can fix this problem by using the `end`

directive in our
print statement:

print(m[r][c],end=" ")

Recall that setting the end character to a space will convert all the newlines into spaces. Our output becomes:

1 2 3 4 5 6

Better, but we need a newline after each row is printed. The easiest way to do this is to print the newline after the inner loop completes:

def displayMatrix(m): rows = len(m) cols = len(m[0]) for r in range(0,rows,1): for c in range(0,cols,1): print(m[r][c],end="") print() return

Now our output becomes:

1 2 3 4 5 6

which is a reasonable approximation to the way a matrix is supposed to look.

Reading a 2-dimensional array from a file is similar to reading a simple array. As a reminder, here is a function for doing just that:

def readArrayOfIntegers(fileName): array = [] s = Scanner(fileName) value = s.readint() while (value != ""): array.append(value) value = s.readint() s.close() return array

This function creates an array,
grows it using *append*, and then returns the
final version of the array.
If the array already exists, things become much simpler;
one can read into the array by using a variation
of the counting pattern:

def readArrayOfIntegers2(array,fileName): s = Scanner(fileName) for i in range(0,len(array),1): array[i] = s.readint() s.close() return # procedure pattern, return value not needed

This second version assumes there is enough data in the file to fill the array. A read error would be generated otherwise. Note that a function that fills a previously constructed array does not require a return value, since the data read from the file is stored in the given array.

If a matrix already exists, then a reading function very similar to
*readArrayOfIntegers2* is easily written by replacing the single loop with
two nested loops:

def readMatrixOfIntegers(matrix,fileName): s = Scanner(fileName) for r in range(0,len(matrix),1): # loop over rows for c in range(0,len(matrix[0]),1): # loop over columns matrix[r][c] = s.readint() s.close() return

As a final note, use of the scanner means that the data in the input file does not need to be organized in matrix form; all the matrix elements could be on a single line, for example.

Matrix patterns are very similar to patterns that loop over simple arrays. For example, here is a filtered-count implementation for a simple array:

def countEvens(items): count = 0 for i in range(0,len(items),1): if (isEven(items[i])): count += 1 return count

The analogous function for 2D arrays is similar:

def countEvens2D(matrix): rows = len(matrix) cols = len(matrix[0]) count = 0 for r in range(0,rows,1): for c in range(0,cols,1): if (isEven(matrix[r][c])): count += 1 return count

Indeed, most of the patterns for 2D arrays follow directly from the simple array versions. Here is an instance of the extreme pattern:

def minValue2D(matrix): rows = len(matrix) cols = len(matrix[0]) min = matrix[0][0] for r in range(0,rows,1): for c in range(0,cols,1): if (matrix[r][c] < min): min = matrix[r][c] return min

Finding the extreme index is a bit trickier since one needs to save
two indices, the row *and* the column of the extreme value:

def minValueIndex2D(matrix): rows = len(matrix) cols = len(matrix[0]) minRow = 0 minCol = 0 for r in range(0,rows,1): for c in range(0,cols,1): if (matrix[r][c] < matrix[minRow][minCol]): minRow = r minCol = c return minRow,MinCol

One can return from the innermost loop, if one knows what one is doing:

def find2D(value,matrix): rows = len(matrix) cols = len(matrix[0]) for r in range(0,rows,1): for c in range(0,cols,1): if (matrix[r][c] == value): return True return False # this return must be outside the outside loop!

Be careful where you place the `return False`

, though.

Although the above examples are rather simple, things can get complicated. Suppose you wished to return the index of the row with the largest sum.

def largestRow(matrix): rows = len(matrix) ilargestSum = 0; largestSum = sum(matrix[0]) # sum the 1st row with a helper for r in range(1,rows,1): s = sum(matrix[r]) if (s > largestSum): ilargestSum = r largestSum = s return ilargestSum def sum(items): total = 0 for i in range(0,len(items),1): total += items[i] return total

Curiously, the *largestRow* function does not appear to follow the pattern of other
matrix functions; it only has one loop over the rows. However, it calls a helper function from
within its loop and that helper function loops over the columns, so we still have our
nested loops.

Although Python and most other programming languages allow for two-dimensional arrays, some restricted languages do not. If you are programming in such a language and need a two-dimensional array, not to worry; two-dimensional arrays can be faked with simple arrays. The trick is to convert a two-dimensional address (row index and column index) into a one dimensional address (simple index).

Consider this matrix:

0 | 1 | 2 | 3 |

4 | 5 | 6 | 7 |

8 | 9 | 10 | 11 |

Using our second attempt at displaying this matrix, we would have obtained the following output:

0 1 2 3 4 5 6 7 8 9 10 11

which looks remarkably like a simple, one-dimensional array! In fact, we can think of this output representing a simple array in which the rows of our two-dimensional array have been stored sequentially.

Now consider extracting the 6 from the 2D version. If our matrix
was bound to the variable *m*, the location of the 6 would be:

m[1][2]

If our simple array version were bound to the variable *n*, then
the 6 can be found at:

n[6]

since the numbers in the array reflect the indices of the array. It turns out that there is a very simple relationship between the 2D address and the 1D address. Since the rows are laid out sequentially in the 1D case and since the row index in the 2D case is 1, that means there is an entire row preceding the row of interest in the 1D case. Since the rows are 4 columns long, then four elements precede the row of interest. The column of interest has two columns preceding it, so summing the preceding row elements and the preceding column elements yields 6, exactly the address in the the simple array!

In general, the index of a 2D location in a 1D array can be computed by the following function:

def simple2DIndex(row,col,rowLength): return row * rowLength + col

Note that this function must know the length of each row in order to make its computation. Note also that the row length is simply the number of columns. If we wished to display a 1D simulation of a 2D array, our display function might look like this:

def displaySimpleMatrix(n,cols): rows = len(n) / cols; for r in range(0,rows,1): for c in range(0,cols,1): print(n[simple2DIndex(r,c)]) print() return

In general, when simulating a 2D array, one replaces all indexing of the form:

m[j][k]

with

m[j * cols + k]

TBW

- Modify the
*displayMatrix*function to print out the vertical bars that delineate a matrix. That is to say, the display function should output something like:| 1 2 3 | | 4 5 6 |

- Modify the
*displayMatrix*function to make the displayed matrix even fancier:+ + | 1 2 3 | | 4 5 6 | + +

- It is relatively easy to transpose a square matrix (a
square matrix has the number of rows and the number of
columns equal). Here is a such a routine:
def transposeSquare(m,size): for r in range(????,???,???): for c in range(???,???,???): m[r][c],m[c][r] = m[???][???],m[???][???] return

Contents |