AP Computer Science - A Digression on Matrices

AP Computer Science Digression into Matrices

Unfinished business

My last article on modulo was a little long winded but let's expand on what we have done on the Matrix1d class. I want to show you how to make methods that perform operations on matrices. Matrix mathmatics are certainly important and whole languages have been created to deal with it. Two languages were discussed in the last article but Matlab is yet another language that deals with mathematics and matrices. It was the language used at MIT recently to do video processing to determine if a person is breathing or not. They created matrix processing routines that amplified the movements of video so they could enhance small motions undetectable to the human eye. So matrix mathematics is certainly a major area of study in Computer Science.

But first there was an error I found in my 'displayMatrix' method when working on the code. It turns out that since we intialized the matrix to be the values of the 1 dimension element. I used just the index in the print statements, giving the apperance of displaying the correct memory locations since the values were the same. However, I should have used the index along with mat1d hence printing mat1d[i], to print the values of the matrix. I fixed it in my code and here is the correct code. I am providing all the mistakes I make to give you the ability to see the common errors even experienced programmers make. I will do so for a few more articles. This will help you find mistakes by reading the code, rather than letting the compiler do all the work. At any rate the new code for displayMatrix follows

void displayMatrix() {
    for (int i = 0; i < this.n * this.n; i++) {
        if (i % n == 0) {
            System.out.println();
        }
        System.out.print(this.mat1d[i] + " ");  // this statement was corrected
    }
    System.out.println();
}

Matrix multiply

Matrices can be multiplied. In our case we are only creating n x n matrices, so multiplication can mean a couple of things. A trivial multiply would be to multiply common elements together and report the new matrix as the individual multiplications. The other multiply is known as Matrix Multiplication (more on that later). First an example to clarify simple matrix multiplication:

1 2      1 3         1 6
3 4  x   2 4    =    6 16

That is pretty straight forward and extending this to the n x n case is trivial. However, what would be helpful would be some methods to access and store based on 2 dimensional indexes. So first lets extend the Matrix1d class to do just that. We already defined a getElement method previously so now we just need a storage method we will call setElement. The definition is as follows:

public int setElement(int r, int c, int value)
{
  int index = (r*this.n) + c
  this.mat1d[index] = value;
}

Syntax error in the above code do you see it?

There is also a bit of a design issue. setElement returns a value of int but why? I'm just setting the value so that should be void. The IDE flagged this when I pasted it so I will change it.

Now the object oriented-ness of this may be a little confusing. I will explain after we plow through making the code. All that is missing is our multiply method so let's code that.

public int simpleMultiply(Matrix1d m)
{
  // check that the current Matrix1d (this) is the same size as the parameter m
  if (this.n != m.n) {  
    // I'm starting to access the fields directly in multiple objects
    // probably time to write getter and setter methods and refactor the code
    // if I am in this code section the matrices are not the same size 
    // return 0 for false the multiplication did not take place
    return 0;
  }

  // If we make it to here the matrices can be multiplied together
  for (int i = 0; i < this.n; i++) {
    for (int j = 0; j < this.n; j++) {
      this.setElement(i,j,this.getElement(i,j)*m.getElement(i,j));
    } 
  }
  return 1;
}

Recode the main method to test this on the 2x2 example above. But wait our Matrix1d class definition does not let us initialize the matrix except by chosing consequtive integers. We could define 2 matrices then use 'setElement' to replace the ones we want. Let's try that first (we will revisit this to allow us to define an array of values to initialize the matrix.

public static void main(String args)
{
  Matrix1d mat1 = new Matrix1d(2);
  Matrix1d ans = new Matrix1d(2);

  // Let's replace the values we need if you look at the 2x2 matrices all that's
  // changed is the 2 and 3 are swapped from their original ordinal positions
  mat1.setElement(0, 0, 1);
  mat1.setElement(0, 1, 2);
  mat1.setElement(1, 0, 3);
  mat1.setElement(1, 1, 4);

  ans.setElement(0, 0, 1);
  ans.setElement(0, 1, 3);
  ans.setElement(1, 0, 2);
  ans.setElement(1, 1, 4);


  if (ans.simpleMultiply(mat1)) {
    ans.displayMatrix();
  }
  else {
    System.out.println("Size error");
  }
}

Now there are 2 not so obvious errors above. The first one is that simpleMutiply returns an int not a boolean (this is something that the C programming language lets you do but Java does not). So we will need to change the if statement to have '== 1' in it. The other is that the String args should be String[] args. Arguments in the main method come in as an array of Strings. So fix those 2 bugs and the output of our multiply routine should be:

1 6 
6 16 

Matrix Multiplication (the real thing)

So while the above is a form of multiplying matrices it is not full blown matrix multiplication. To multiply 2 matrices in it's standard meaning means to multiply the rows of one matrix with the columns of the other and sum the terms to form new elements of the matrix that will become the answer. So if A and B are the matrices I want to Matrix Multiply and I will use C as the new matrix obtained by the operation. Matrix multiplication is defined as follows:

C_i,j = Σ A_i,k * B_k,j (k = 0,…,n-1)

To program this you will need 3 nested loops. Two (2) nested loops for the i and j of each element of C and an inner loop inside of those to sum up all the k multiplications.

public Matrix1d matrixMultiply(Matrix1d b)
{
  // Object oriented I will use the A object to do the calculation give it B
  // and return a new matrix for the return value which of course is C
  // Create C
  Matrix1d c = new Matrix1d(this.n);

  for (int i =0 ; i < this.n; i++) {
    for (int j = 0; j < this.n; j++) {
      c.setElement(i,j, 0); //zero out the element to accumulate the sum
      for (int k = 0; k < this.n; k++) {
        c.setElement(i, j, c.getElement(i,j) + this.getElement(i,k) * b.getElement(k,j);
      }
    }
  }
  return c;
}

Mistake above. Fixed in final version again see if you can sight read and find the error.

Interestingly enough in our representation of a matrix as a linear array we only need modulo in order to display rows and columns given the internal index of the array. If I didn't need to display this in matrix form I could almost write an entire matrix package without modulo. However, in the routines to convert a row and column into an index modulo is implicit. If you notice we use the formula:

array index = divisor * quotient + remainder

What is the remainder? Of course the answer we get when doing a modulo operation.

A better way of setting up a matrix

The use of setElement calls is a little cumbersome. It would be nicer if a list of numbers could be input directly and the class would take care of placing them in the storage array directly. This is easy enough to accomplish by creating a new constructor that allows an int array to be the parameter.

Matrix1d(int size, int[] vals)
{
  // vals size would have to be a square of some n that needs to be 
  // determined. For now rather than handling an error just assume only
  // an appropriately sized array is given and that the size of the 
  // matrix is provided as a parameter

  this.n = size;
  this.mat1d = vals;

}

Add the following statements to the main method to test:

// Test the array initialization
int[] matarr = {2,4,6,8,10,12,14,16,18};
Matrix1d mat2 = new Matrix1d(3,matarr);
mat2.displayMatrix();

Identity Matrix

Just as 1 x n = n (multiplicative identity). So to in Matrix Multiplication there exists an Identity Matrix we can call 'I' that creates a matrix multiplicative identity: A x I = A. Pretty interesting, let's see if our newly created matrix class is up to the task. First what does the Identity Matrix look like? It's a matrix of nxn elements with 1's in the diagonal spaces from 0,0 .. n,n.

1 0 0     1 0 0 0 
0 1 0     0 1 0 0 
0 0 1     0 0 1 0
          0 0 0 1

The preceding are 3 x 3 and 4 x 4 identity matrices We can use our new constructor to create an identity matrix. Add the following lines to main to test the constructor

int[] identity3 = {1,0,0,0,1,0,0,0,1};

Matrix1d mat3 = new Matrix1d(3,identity3);
Matrix1d mat4 = mat2.matrixMultiply(mat3);
mat4.displayMatrix();

Output

1 6 
6 16 

7 10 
15 22 

2 4 6 
8 10 12 
14 16 18 

2 4 6 
8 10 12 
14 16 18 

Let's modify main to printout the identity matrix as well. The final version of the main method is:

    public static void main(String[] args) {
        Matrix1d mat1 = new Matrix1d(2);
        Matrix1d ans = new Matrix1d(2);

        // Let's replace the values we need if you look at the 2x2 matrices all that's
        // changed is the 2 and 3 are swapped from their original ordinal positions
        // and the other corner elements are 1 and 4 respectively
        mat1.setElement(0, 0, 1);
        mat1.setElement(0, 1, 2);
        mat1.setElement(1, 0, 3);
        mat1.setElement(1, 1, 4);

        ans.setElement(0, 0, 1);
        ans.setElement(0, 1, 3);
        ans.setElement(1, 0, 2);
        ans.setElement(1, 1, 4);

        if (ans.simpleMultiply(mat1) == 1) {
            ans.displayMatrix();
        } else {
            System.out.println("Size error");
        }

        Matrix1d mmult = mat1.matrixMultiply(mat1);
        mmult.displayMatrix();

        // Test the array initialization
        int[] matarr = {2,4,6,8,10,12,14,16,18};
        Matrix1d mat2 = new Matrix1d(3,matarr);
        mat2.displayMatrix();

        int[] identity3 = {1,0,0,0,1,0,0,0,1};

Matrix1d mat3 = new Matrix1d(3,identity3);
Matrix1d mat4 = mat2.matrixMultiply(mat3);
mat3.displayMatrix();
mat4.displayMatrix();

Output

1 6 
6 16 

7 10 
15 22 

2 4 6 
8 10 12 
14 16 18 

1 0 0 
0 1 0 
0 0 1

2 4 6 
8 10 12 
14 16 18 

Conclusion

That's all for matrices for now. This should give you some exposure of how we use computers to solve math problems. We basically try to model what we do in math and make the computer go through the tedious processing. Next we will revisit modulo in a more interesting way.

References

1. Eulerian Video Magnification MIT CSAIL web address: http://people.csail.mit.edu/mrub/vidmag/

Final Version of Code

public class Matrix1d {

    int n = 10;
    int mat1d[] = null;

    public Matrix1d(int n) {
        this.n = n;
        this.mat1d = new int[this.n * this.n];
        // intialize the elements to count up from 0
        for (int i = 0; i < this.n * this.n; i++) {
            mat1d[i] = i;
        }
    }

    public Matrix1d(int size, int[] vals)
{
  // vals size would have to be a square of some n that needs to be 
  // determined. For now rather than handling an error just assume only
  // an appropriately sized array is given and that the size of the 
  // matrix is provided as a parameter

  this.n = size;
  this.mat1d = vals;

}

// put our code to get an element here
    int getElement(int row, int col) {
        return this.mat1d[row * this.n + col];
    }

    void display() {
        int r, c;

        for (int i = 0; i < this.n * this.n; i++) {
            r = i / this.n;   // integer divide gives us the row for the element

            // for the column it's the left over after the integer divide
            // col = i - (r * n) which sin r was calculated with int division is just
            // the remainder. Well since we want to look professional we know that's 
            // modulo. So to look like we know what's going on let's use modulo
            c = i % this.n;
            System.out.println("matrix[" + r + "][" + c + "] = " + this.mat1d[i]);
        }
    }

    void displayMatrix() {
        for (int i = 0; i < this.n * this.n; i++) {
            if (i % n == 0) {
                System.out.println();
            }
            System.out.print(this.mat1d[i] + " ");
        }
        System.out.println();
    }

    public void setElement(int r, int c, int value) {
        int index = (r * this.n) + c;
        this.mat1d[index] = value;
    }

    public int simpleMultiply(Matrix1d m) {
        // check that the current Matrix1d (this) is the same size as the parameter m
        if (this.n != m.n) {
            // I'm starting to access the fields directly in multiple objects
            // probably time to write getter and setter methods and refactor the code
            // if I am in this code section the matrices are not the same size 
            // return 0 for false the multiplication did not take place
            return 0;
        }

        // If we make it to here the matrices can be multiplied together
        for (int i = 0; i < this.n; i++) {
            for (int j = 0; j < this.n; j++) {
                this.setElement(i, j, this.getElement(i, j) * m.getElement(i, j));
            }
        }
        return 1;
    }

    public Matrix1d matrixMultiply(Matrix1d b)
{
  // Object oriented I will use the A object to do the calculation give it B
  // and return a new matrix for the return value which of course is C
  // Create C
  Matrix1d c = new Matrix1d(this.n);

  for (int i =0 ; i < this.n; i++) {
    for (int j = 0; j < this.n; j++) {
      c.setElement(i,j, 0); //zero out the element to accumulate the sum
      for (int k = 0; k < this.n; k++) {
        c.setElement(i, j, c.getElement(i,j) + this.getElement(i,k) * b.getElement(k,j));
      }
    }
  }
  return c;
}

    public static void main(String[] args) {
        Matrix1d mat1 = new Matrix1d(2);
        Matrix1d ans = new Matrix1d(2);

        // Let's replace the values we need if you look at the 2x2 matrices all that's
        // changed is the 2 and 3 are swapped from their original ordinal positions
        // and the other corner elements are 1 and 4 respectively
        mat1.setElement(0, 0, 1);
        mat1.setElement(0, 1, 2);
        mat1.setElement(1, 0, 3);
        mat1.setElement(1, 1, 4);

        ans.setElement(0, 0, 1);
        ans.setElement(0, 1, 3);
        ans.setElement(1, 0, 2);
        ans.setElement(1, 1, 4);

        if (ans.simpleMultiply(mat1) == 1) {
            ans.displayMatrix();
        } else {
            System.out.println("Size error");
        }

        Matrix1d mmult = mat1.matrixMultiply(mat1);
        mmult.displayMatrix();

        // Test the array initialization
        int[] matarr = {2,4,6,8,10,12,14,16,18};
        Matrix1d mat2 = new Matrix1d(3,matarr);
        mat2.displayMatrix();

        int[] identity3 = {1,0,0,0,1,0,0,0,1};

Matrix1d mat3 = new Matrix1d(3,identity3);
Matrix1d mat4 = mat2.matrixMultiply(mat3);
mat3.displayMatrix();
mat4.displayMatrix();
    }
}

Author: Nasty Old Dog