R Basic Vector/Matrix Stuff (for the Statistically Inclined but Computer Programming Challenged)

Introduction

After some feedback on my previous R blog I have found that a 'Newbie' R/Statistics person needs to have a better foundation in the Vector arithmetic and representation that is the foundation of R. I thought the cursory look provided in my previous blog would suffice. I realize now that R provides multiple ways of accessing Vectors and Matrices (esp. Matrices) that hide the "Vectorness" that is inherent in the language. There are many thing in R that older programmers have already had experience with. The original vector language developed by IBM was known as APL. Dr. Ken Iverson developed a specialized math syntax while at Harvard. IBM hired him to implement that syntax into a computer programming language (Original concepts detailed in reference [2]). This all happened in the 1960s. For those that learned Computer Science in the 60s and 70s they would have had exposure to this language. It has continued on and there is even a free GNU version available today[6]. The problem for many people was the strange symbols that were the basis of the language. Since APL there have been many offshoots that have carried forward this idea of 'Vectors' being the built in data structure of the language but with a design change that uses standard characters found on your standard keyboard for syntax. The language K is probably the most successful commercial implementation of this offshoot[3]. R is probably the most successful open source implementation of these concepts. My personal favorite is the J language which the late Dr. Iverson developed as a redesign of his APL concepts. J has an active user forum and a great collection of articles on their website on the history of APL, Dr. Iverson and many technical articles showing various uses of J in many different areas(see reference [1]).

This history that many Professors and teachers experienced first hand make it difficult for them to explain. It is very easy to assume that something is a simple concept because you forget that you didn't learn it in R. You learned it in some other computer language, programming different types of things. Jumping into R was not that difficult and you appreciate how R has transformed some of the menial tasks into simple function calls. For the 'Newbie' they are left with many WTF moments as things seem to happen by magic. The goal of this blog post is to show you how the basic vector concepts are in everything that you do. This will help you as you try to dissect your data stored in a table. R has many layers on that data that help facilitate creating charts and statistics, but in the end it is all just vectors and matrices (aka arrays and tables).

Vectors/Arrays

A vector has its roots in physics. The idea behind it is that many physical properties are described by a value and a direction. I may push something along at 25 miles per hour but that is only part of the story. I am also pushing it along in a certain direction. Once I come up with a way of telling direction I now must carry 2 values along to let you know exactly what I am doing. So the concept of a vector is a way of carrying around multiple values to describe a single concept. In math and in computers it's not hard to envision that we might want to carry around more than just 2 values. Why not 3? There are after all 3 dimensions. Why not 10? Why not 1000? Hence for our purposes a vector is a way of carrying around multiple pieces of information and referencing them by a single name and an index. Mathematics uses a subscript to identify a particular item in a vector:

\[x = {2,4,6,8}\] \[x_1 = 2 \] \[x_4 = 8 \]

In R access to individual vector elements is accomplished as follows:

> x = c(2,4,6,8) #combine 2 4 6 8 into a vector and store it in x
> x
[1] 2 4 6 8
> # since subscripting is a pain in the neck R uses square brackets
> x[2]
[1] 4
> x[1]
[1] 2
> x[4]
[1] 8
> 

Seems easy enough. In math rather than write out every element of a vector we can use an ellipsis to continue an established pattern. So for example to represent the numbers from 1 to 100 in a vector in Math we do the following:

\[x = {1,2,3,4,\ldots,99,100} \] \[x_3 = 3 \] \[x_{98} = 98 \]

R rotates the ellipsis and uses the ':' (the colon) to implement similar functionality:

> x = c(1:100)
> x
  [1]   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21
 [22]  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42
 [43]  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
 [64]  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84
 [85]  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99 100
> x[3]
[1] 3
> x[98]
[1] 98
> 

Now here is where R can be deceiving. The colon operator is like the ellipsis but not exactly alike. The colon is only good for generating an increment by one pattern. So for example in math

\[ x = {2,4,6,\ldots,20,22} \]

You instinctively understand I mean to count by 2's up to 22. Trying this in R with the colon operator just increments by 1s from 6 to 20:

> x = c(2,4,6:20,22)
> x
 [1]  2  4  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 22
> # from 6 to 20 R counts by 1s it doesn't try to infer my pattern 

Now that doesn't mean I have to enter in every value for R if I want to count by 2's. But it does mean I have to be more arithmetically distinct in what I tell R to do. Counting by 2's is just counting by 1's up to half the maximum value and multiplying the result by 2. So to accomplish the same thing in R:

> x = 2 * c(1:11)
> x
 [1]  2  4  6  8 10 12 14 16 18 20 22
>

R does do one bit of inference with this operator:

> # one thing R will infer is that if you reverse the order and put the larger number first
> # R will count backwards for you
> x = c(11:1)
> x
 [1] 11 10  9  8  7  6  5  4  3  2  1
> 

But if R didn't do this, it would be easy to reconstruct with some added R functionality: the reverse function 'rev'. This function gives the reverse order of a vector

> # Create a reverse order without switching
> x = c(1:11)
> x
 [1]  1  2  3  4  5  6  7  8  9 10 11
> rev(x)
 [1] 11 10  9  8  7  6  5  4  3  2  1
> # in one line
> x = rev(c(1:11))
> x
 [1] 11 10  9  8  7  6  5  4  3  2  1
> 

I hope at this point you can extrapolate and realize that by investigating the functions available in R we can create our own vectors of data without having to resort to reading it in from a file. This comes in handy for putting together some simple testing data.

Matrix/Matrices

A Matrix wasn't originally a computer driven reality to enslave people to provide power to machines. It is just a mathematical concept for a table of values. It is an extension of the concept of a vector. While a vector has multiple values it is considered a one-dimensional object. This means I only need one index to obtain a value. If I took a set of vectors of the same length and piled them on top of each other I would create a table or Matrix. In mathmatics notation you just put a table of numbers in parenthesis:

\[ M = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 11 & 12 & 13 & 14 & 15 \\ 21 & 22 & 23 & 24 & 25 \end{pmatrix} \]

\[ M_{1,2} = 2 \] \[ M_{3,3} = 23 \]

Matrices can be created directly in R. But first a little segue to go from vectors to matrices In R start by creating 3 vectors of 5 elements each. Vector1 = {1,2,3,4,5}, Vector2={11,12,13,14,15} and Vector3={21,22,23,24,25}. To save typing call them V1, V2, and V3. Here is the R session to set that up.

> # 3 Vectors of length 5 (notice I use a little math to help create different values)
> V1 = c(1:5)
> V2 = 10+V1
> V3 = 20+V1
> V1
[1] 1 2 3 4 5
> V2
[1] 11 12 13 14 15
> V3
[1] 21 22 23 24 25
> # notice that R added a number to the whole vector V1
>

Even though I had to type each variable to display the data, notice the natural tabular form that appears when looking at the last 3 lines of numbers above. They look like 3 rows of a table. If I wanted the second element of the first row, the 4th element of the second row and the 1st element of the third row. I could access them all as follows (continuing with the vectors I have set up):

> V1[2]
[1] 2
> V2[4]
[1] 14
> V3[1]
[1] 21
> 

I named the vectors with numbers purposefully. If I could form a table and R could extend it's access to account for rows and columns (which it does) I could use one variable name and access any element by just giving the row and column number of that element. V1[2] would be M[1,2] in a table constucted of these vectors and stored in M. Similarly V2[4] -> M[2,4] and V3[1] -> M[3,1] Not only do I save typing but I can also create loops that would be able to go through every member in the matrix in almost any conceivable order I can imagine making looping programs do.

Experimenting with R and its matrix creation function I was able to use the vectors to create a table with each vector above as one row. I did have to use the matrix transpose function 't' (initially). Transpose will flip the matrix by swapping rows for columns (look up matrix transpose if you don't quite understand what it's doing from the session below). In the end I figured out the proper parameters for the matrix function to pile the vectors on top of each other (in row fashion) in one fell swoop.

> # Use matrix function to create a matrix from V1, V2, and Ve
> M = matrix(c(V1,V2,V3),nrow=3,ncol=5)
> M
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    4   12   15   23
[2,]    2    5   13   21   24
[3,]    3   11   14   22   25
> # matrix fills columns first not rows what to do?
> t(M)
     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    4    5   11
[3,]   12   13   14
[4,]   15   21   22
[5,]   23   24   25
> # Lets flip the dimensions around and see what happens
> M = matrix(c(V1,V2,V3),nrow=5,ncol=3)
> M
     [,1] [,2] [,3]
[1,]    1   11   21
[2,]    2   12   22
[3,]    3   13   23
[4,]    4   14   24
[5,]    5   15   25
> # since matrix fills columns first lets fill a vector per column by switching dimensions
> # like above. Now transpose should get us the form we were looking for which is a 
> # vector per row
> t(M)
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    2    3    4    5
[2,]   11   12   13   14   15
[3,]   21   22   23   24   25
> # so lets put it all into one line to make a matrix of our three vectors with each
> # vector in its own row
> M = t(matrix(c(V1,V2,V3),nrow=5,ncol=3))
> M
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    2    3    4    5
[2,]   11   12   13   14   15
[3,]   21   22   23   24   25
> # Now M[1,2] should match V1[2], M[2,4] = V2[4] and M[3,1] = V3[1]
> M[1,2]
[1] 2
> V1[2]
[1] 2
> M[2,4]
[1] 14
> V2[4]
[1] 14
> M[3,1]
[1] 21
> V3[1]
[1] 21
> # Had I dug a little deeper into the matrix function there is a flag to fill by called 'byrow'
M = matrix(c(V1,V2,V3),nrow=3,ncol=5,byrow=TRUE)
> M
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    2    3    4    5
[2,]   11   12   13   14   15
[3,]   21   22   23   24   25
> # got the matrix in 1 step

The above session has an important nuance. I assumed that R would think the way I do: Put vectors into rows. But as the session unfolded it was clear that R is column oriented by default. I was able to adjust once I saw the way R was doing things. This is important! As you begin to think in terms of vector and matrix operations you may find your answer coming from R is not formatted properly or the data doesn't seem to have the right appearance. When you see wierd things happening you must break down your operations and make sure you and R are on the same page (more so you since R is not going to change). When in doubt go to one operation per line, display the results of each operation (or a portion thereof if you have a considerable amount of data). Verify that each operation you are performing is what you expect. You would be surprised how one small typographical error can cause you hours of debugging and anxiety. Your mind will overlook the small error because it will fill in a missing operation as you are looking at it (or ignore it if there is an extra operation). By breaking it down you are verifying to yourself that each operation works as intended.

Row and Column names

I use term 'table' above rather loosely above. Don't confuse this with any add-on packages that have tables. I mean it in the simplest sense as a way of describing 2 dimensional data. R has another table type structure called a 'data frame'. So what's the difference between a matrix (which I have shown as a 'table' of numbers) and an R data frame? In an R data frame you can have a mix of data types between columns. Each individual column needs to have data of the same type but the next column can have a completely different datatype (as long as it's consistent within that column). So in a matrix all the data must be the same across all rows and columns and in a data frame there can be some mixing of data types on a column by column basis.

Now you access data in a 'data frame' by indexing the same way as you do with a matrix. The trick is not to do any operation on that data that is inconsitent with the datatype of the column. So in a matrix (since all the data is the same type) I can add together any 2 selected elements (if the data is of numeric type).

> # Create a vector of 25 elements from 1 to 25
> v <- 1:25
> v
 [1]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
> # Use vector v to create a matrix that is 5x5 of those elements
> m <- matrix (v,5)
> m
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    6   11   16   21
[2,]    2    7   12   17   22
[3,]    3    8   13   18   23
[4,]    4    9   14   19   24
[5,]    5   10   15   20   25
> # Add m[2,3] and m[3,2] together
> m[2,3]
[1] 12
> m[3,2]
[1] 8
> m[2,3]+m[3,2]
[1] 20
>

Nothing surprising. I make a matrix of integer values and I can add them together any way I please.

What about naming columns and rows? Here it turns out there are multiple ways of naming columns and rows depending if the underlying data structure is a matrix or 'data frame'. The following calls work the same across all of those structures. A 'data frame' has a built in $ operator it is used to access a whole column of data in a 'data frame' by name. I include its use the session below:

> # Give names to the columns and rows
> m
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    6   11   16   21
[2,]    2    7   12   17   22
[3,]    3    8   13   18   23
[4,]    4    9   14   19   24
[5,]    5   10   15   20   25
> colnames(m) <- c("C1","C2","C3","C4","c5")
> m
     C1 C2 C3 C4 c5
[1,]  1  6 11 16 21
[2,]  2  7 12 17 22
[3,]  3  8 13 18 23
[4,]  4  9 14 19 24
[5,]  5 10 15 20 25
> # Now the rows
> rownames(m) <- c("r1","R2","r3","R4","r5")
> m
   C1 C2 C3 C4 c5
r1  1  6 11 16 21
R2  2  7 12 17 22
r3  3  8 13 18 23
R4  4  9 14 19 24
r5  5 10 15 20 25
> # We can still access with number indexes as before
> m[2,3]
[1] 12
> # But now we can use names as indexes instead
> m ["R2","C3"]
[1] 12
> # Is this where we can start using the $ in the variable name?
> m$C2
Error in m$C2 : $ operator is invalid for atomic vectors
> # No we can't use that type of access for a matrix
> # Turn m into a dataframe d and see what we can do
> d <- as.data.frame(m)
> d
   C1 C2 C3 C4 c5
r1  1  6 11 16 21
R2  2  7 12 17 22
r3  3  8 13 18 23
R4  4  9 14 19 24
r5  5 10 15 20 25
> # It doesn't look that much different but here are the different ways
> # to access data.
> d[2,3]
[1] 12
> d["R2","C3"]
[1] 12
> d["R2",]$C3
[1] 12
> d$C3
[1] 11 12 13 14 15
> d[2,]
   C1 C2 C3 C4 c5
R2  2  7 12 17 22
> d["R2",]
   C1 C2 C3 C4 c5
R2  2  7 12 17 22
> 

Data Frames

The data frame's strength comes from being able to handle tabular data of different data types. The following session creates a data frame with a mix of data types and shows how you have to be careful what operations you choose to do. By supplying column names in the creation of the 'data frame' there is no need to perform a separte operation to insert them into the 'data frame'.

> d2 <- data.frame(C1=c(1:5),C2=c("a","b","c","d","e"),C3=c("john","joesph","james","jane","janet"))
> d2
  C1 C2     C3
1  1  a   john
2  2  b joesph
3  3  c  james
4  4  d   jane
5  5  e  janet
> d2[1,1]+d2[3,1]
[1] 4
> d2[1,1]+d2[1,2]
[1] NA
Warning message:
In Ops.factor(d2[1, 1], d2[1, 2]) : ‘+’ not meaningful for factors
> # We can do some comparisons on the character data
> "a" == d2[2,2]
[1] FALSE
> "a" == d2[1,2]
[1] TRUE
> "james" == d2[3,2]
[1] FALSE
> "james" == d2[3,3]
[1] TRUE
> d2[1,]
  C1 C2   C3
1  1  a john
> d2$C2
[1] a b c d e
Levels: a b c d e
> 

The other strength of a 'data frame' is that it can be used seamlessly with functions that read in comma separated values. This allows you to pull in data sets from databases or websites and operate on them easily. Since comma separated value files usually include a first line of column names, the 'data frame' will already have column names inside after a read operation.

Conclusion

These topics are covered in more depth in the pdf text "An Introduction to R" [7]. Hopefully this blog has provided some insight into the workings of R and vector languages in general. The purpose here was to give just enough vector stuff to get you through debugging a statistics assignment when things go wrong. Usually the data is structured in a manner that's different from how your mind is perceiving it. This causes you to make improper function calls. I can't say this enough when in doubt break things down! Try functions on smaller pieces of data and make sure you get an answer you expect. Once things are operating the way you expect you can extrapolate up to larger datasets.

References

1. http://www.jsoftware.com/ great vector based language. Excellent forum to search various subjects. There is an R interface to the J language so you can work in J and use R when you need something statistical that J doesn't have. Search the website for Ken Iverson they have some execellent essays on the beginnings of APL and vector languages
2. Iverson, Kenneth E. “A Programming Language.” A Programming Language, J Software Inc., 13 Oct. 2009, www.jsoftware.com/papers/APL.htm.
3. https://kx.com/ The company that produces the K-language and Kdb (a database based on the K-language)
4. http://www.r-tutor.com/ offers nice tutorials on various aspects of R. It also has some nice deep-learning info. Always seems to come up first when googling an R language reference
5. https://stackoverflow.com/questions/2281353/row-names-column-names-in-r discussion on matrix and dataframe row and column names
6. https://www.gnu.org/software/apl/ GNU's apl implementation
7. https://cran.r-project.org/doc/manuals/r-release/R-intro.pdf A good general (not so statistical) introduction to the language that covers many of these details in greater depth. It's a PDF you should download a copy

Author: NASTY OLD DOG

Validate

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

Modulo

AP Computer Science Modulo it's Just Remainder

Think Mathematically

Computer Science is technically a branch of Mathematics and yet pure mathematical thinking may cause problems when you try to understand the temporal relationships (temporal fancy word for timing) of computer programing. For example if you try to understand the following (based on your understanding of algebra):

j = j + 1

The above statement makes no sense, algebraically. But in Computer Science this really means take the current value of j add 1 to it, store the answer back in j. In Programming names are not algebraic variables they are memory locations whose value depends on the timing of instructions. When the above example gets compiled the instructions to the computer get ordered in a certain way and the processor acts on each statement one at a time in the order they are found. It is confusing to the beginning Computer Scientist because they have years of mathematics where the variable was only going to be one value and it was their job to find out what it is.

Another human thought process getting in our way is the fact that we read English from left to right. For the human to understand what is happening they have to read in the whole sentence then work backwards:

• Start on the expression on the right hand side
  • interpret what is happening here (j + 1)
• Then figure out what will happen because of the equals sign

The late Ken Iverson realized this back in the early 1960's Dr. Iverson created a whole notation that would allow a mathematician to represent algorithms. The seminal treatise was captured in his book A Programming Language. IBM hired Dr. Iverson to implement this notation on a computer. He created a new programmming language called APL.

Dr. Iverson came up with a brilliant realization (among many) that our traditional way of resolving precedence (the order we do operations in mathematics) was in reality arbitrary and ambiguous. While most computer languages (like Java) strived to duplicate tradition, Dr. Iverson¹ said there is no operator precedence we just read a statement from RIGHT to LEFT (yes the opposite of what you've been taught all these years) and do the operation when we first hit it. If the programmer needs to ensure certain operations happen first rewrite your equation or use parenthesis to organize which operations go first (so parentheses are the same in any language). The beauty of this realization in our simple example above, reading Right to Left gives us a sense of the temporal considerations when running the program.

1 is added to j and the result stored back in j

Reading right to left provides a better understanding of what happens and when. You begin to think more about how the computer sees things. Java uses a traditional precedence mechanism for mathematical formulas. Reading right to left will not be that helpful for complex statements.

The budding computer scientist needs to be ready to think mathematically in non-traditional ways. Indeed, Dr. Iverson even invented new mathematic symbols and had to create his own font to even print the new operations. He was striving for a new mathematical world where the opertator relationships would be defined in a standard way so you could map your mathematical talents and apply them to a computer in a useful way. This is much the same as Dirac notation for quantum mechanics or Laplace transforms for differential equations. Create a new mathematics that abstracts away tedious details and helps the mathematician to think and get their hands around a new environment.

When you are able to map your mathematics skills into solving the programming assignments, you will be surprised at your own intuition and creativity. You will be able to simplify a problem because you saw the mathematical tricks that reduced 100 lines of code down to 10.

Tricks of the Trade: Modulo

One computer math trick you need to be aware of is modulo. There are many reasons to use Modulo. Indexing into 2 dimensional arrays (matrix after its mathematical counterpart) as an example. It is usually used when we are trying to map large a set of numbers into a smaller set. Many indexing operations will take advantage of modulo (the Java operator %). Modulo is rooted in long division. You know what it is and what it does even if you don't recognize the name.

Modulo = Remainder

Remember doing long division all those years ago in Elementary School? You used an algorithm and your knowledge of the "times" tables and would come up with 2 answers. One was the quotient the other was the remainder. The amount of stuff left over since the division did not go in evenly.

Remainder was always a throw away item in school we reported it but didn't use it very much. But it turns out it's very useful in many aspects of programming. In fact for games you use it all the time with out knowing about it. Most random number generators use modulo by a prime number. In fact the very architecture of the CPU registers has modulo built in. If you were to add 10 to (2³²-1) you would overflow the register but the number left in the register would wrap around 0 and what would be left is 9.

The best thing about modulo is it's a built in mathematics operation. If we had to duplicate the functionality programatically it would make our code too complex. The reality is that complex code is error prone code and we may not take into account every eventuality. By using computer mathematics we have a much better likelihood the code will operate properly. Hopefully by using a mathmatics solution there will be much smaller set of lines of code to debug. It's much easier to find a mathematical error in one line than a logic error in multiple nested if statements

First Example Simulating Multidimensional Arrays

Let's pretend Java didn't provide the ability to declare multidimensional arrays. But they do give us single dimensional arrays. For simplicity sake lets just simulate square matrices (NxN).

Specifications

1. Call the class Matrix1d
2. Using only one array field and any number of individual support fields
3. The actual elements shall be 'int's just to simplify
4. Create a class that constructs a 2 dimensional array given the size N
5. Use Method getElement(int row, int col)
6. Create a display method display() that prints a list of elements and their indexes and prints the matrix in standard matrix format

Lets work on 4 first. There are N columns so the first N elements of the 1d array should represent the first row of the matrix. The second row would be the next N elements … the Nth row would be the last N elements. You should be able to figure out the equation to map a row and column into a single address in our 1d array:

row * N + col

The code for this is:

int getElement(int row, int col) 
{
  return this.mat1d[row * this.n + col];
}

Let's store N in field int n and using the mat1d name for the array let's code the class so far with a possible constructor:

class Matrix1d {
int n = 10;
int mat1d[] = null;

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;
  }
}

// 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%n
    println("matrix["+r+"]["+c+"] = " + mat1d[i];
  }
}

Now the above code has a few syntax errors in it.

• I'm missing public in front of my class definition
• I forgot a semicolon in the 4th line from the bottom (c = i%n)
• I'm missing the close parenthesis int the println statement and the 'System.out.' before the println

Now these are mistakes you make all the time that the IDE (eclipse, netbeans, etc) point out to you immediately. How did I get the code with those mistakes? Because I coded it in a separate editor I use to write these blog articles and then copied the code and pasted it into Netbeans. Rather than fix my article I thought I would point out to you that you can program outside of the IDE. It's actually helpful to your design. Code out large chunks of code, think about what you want to do, then as a separate step (once you have your logic in place) fix the syntax. It helps to keep you focused on your real problem instead of being side tracked by fixing semicolons or missing keywords.

There is also another problem above in my style of coding Java I am missing 'this.' on my fields. Instead I am addressing them directly by name. I find it helpful to reference object fields by using the 'this' keyword. It is a reminder that this code takes place inside an object. That object would have been constructed somewhere else in the code by calling 'new' on the constructor in the class definition for the object.

Ultimately in object oriented programming fields should be addressed directly as little as possible (even using the 'this' directive). Indeed, I would normally refrain from using them at all and instead implement 'getter' and 'setter' methods to change and access the fields. Now you may be thinking: "It seems kind of dumb for such a simple program" and I agree. For this simple program it's not necessary and only adds clutter to the code with out expressing any central logic. This again is why I like to prepend 'this' to the field. It's a reminder that if this simple little program actually becomes part of a library that another programmer would use, it needs to be buffed up with 'getter' and 'setter' methods and replace my direct references to object fields using the get and set method calls.

Now let's add a main method to test the class so far:

static void main(String[] args)
{ 
  // Create a 5 x 5 matrix
  Martix1d mymatrix = new Matrix1d(5);

  mymatrix.display();
}

Again I just coded this directly in my article editor now I will copy and paste into the IDE and see what mistakes pop up.

There are two mistakes in the main method code see if you can find it.

In the meantime once I fixed all the mistakes in the code above here is what we get as the output:

matrix[0][0] = 0
matrix[0][1] = 1
matrix[0][2] = 2
matrix[0][3] = 3
matrix[0][4] = 4
matrix[1][0] = 5
matrix[1][1] = 6
matrix[1][2] = 7
matrix[1][3] = 8
matrix[1][4] = 9
matrix[2][0] = 10
matrix[2][1] = 11
matrix[2][2] = 12
matrix[2][3] = 13
matrix[2][4] = 14
matrix[3][0] = 15
matrix[3][1] = 16
matrix[3][2] = 17
matrix[3][3] = 18
matrix[3][4] = 19
matrix[4][0] = 20
matrix[4][1] = 21
matrix[4][2] = 22
matrix[4][3] = 23
matrix[4][4] = 24

Did I happen to mention Modulo?

Please review the code so far as it pertains to Modulo. You need to see how modulo is taking a single number and converting it into a column index. This is believe it or not a non-trivial use of a computer program. If you enter the field or do electronics as a hobby you may have to program in a language that doesn't have multidimensional arrays. But that shouldn't stop you from making them yourself out of the tools you do have available. If the project you are working on needs multi-dimensional arrays to simplify the code build your own.

Certainly Java has multidimensional arrays. But what if you wanted to fill the contents of a multidimensional array with the values in a 1 dimensional array? How would we do that? We could adapt our code without much of a problem, but how would you do it if you weren't an expert with modulo?

Better Display or at least more mathematical display

For those of you who have already been introduced to matrices you will agree that our display method does not look like a matrix in a math book. Let's create a new method call displayMatrix that will display the values in rows or columns we don't need the indexes. But we will use modulo to tell us when to start printing elements in a new row. I won't go into the design but try to do it yourself. I provide my solution with the full code listing. One problem with the output from my implementation below, the matrix printed out isn't very square. Single digit numbers get different spacing than double digit. I'll address that in the next installment.

Conclusion

I'm not finished with modulo 2 more articles are coming one to implement 2 dimensional arrays as a Java multidimentional array and fill it with consecutive numbers or from numbers in a single dimensional array. Modulo will play a role there. The second article will be a Blackjack program and how modulo helps us to determine the type of card ace through ten, jack, quesn, king. Modulo will also help determine the suit spades, diamonds, clubs, hearts.

I hope that my taking you through an actual design process didn't bore you to much. I will probably continue in that vein because these programs don't go from mind to paper with out some syntax errors. I thought it might be helpful to you to see how some one else thinks through the process and how far they take it before commiting to compile the code.

/**
 *
 * @author Nasty Old Dog
 */
public class Matrix1d {

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

    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;
        }
    }

// 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(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a 5 x 5 matrix
        Matrix1d mymatrix = new Matrix1d(5);

        mymatrix.display();
        mymatrix.displayMatrix();
    }
}

References

1. Iverson, K.E., A Programming Language, Wiley, 1962-05. Available at J Software Site

Footnotes:

¹ The late Dr. Iverson's work lives on at a company he created: J Software. He also updated APL (so to speak) with it's sister the programming language J. J has versions for most platforms even the iPhone and iPod. The difference between J and APL is that J reverts back to standard characters yet all of the interesting operators are there. Dr. Iverson also improves on APL in the terminology used to describe the language. Dr. Iverson maps the language contructs into English grammar equivalents. This way comments are started by NB. the english equivalent for NB note bene (note well), operators are now verbs, Variables are nouns, etc. It's a great language one I highly recommend. Read more at http://wwww.jsoftware.com

By the way in J the operator, I mean verb, for modulo is called residue and it uses the "|" symbol instead of a "%" like in Java. You also must put the numbers in reverse, why because the entire language J is read from Right to Left. So the J equivalent of Java's 121%5 would be 5|121. You may think it's confusing, I prefer to think of it as amazing that I can change the way a computer does things to suit my whims and fancies.

Author: Nasty Old Dog