Tags

, , , , , , ,

… It’s been a while, but here we go!

This article is to give a short introduction to matrices and describe how to perform some manipulation on them in the computer programming context; for matrices and rotation in the algebraic context you can always trust Wikipedia.

Regarding programming and algorithms in general, there is a high probability that you would end up involving matrices to store and manipulate data. Although some high level programming languages have support for more sophisticated mechanisms than arrays or matrices (like dictionaries or maps), exercise your skills to manipulate multidimensional arrays is always good for your abstraction.

I’m including a quick explanation of matrices, here’s the section regarding the manipulation and here you can see directly the conclusion with the functions to do the rotation of matrices.

First part, what is a matrix? No, not the Wachowskis movie…

In programming an array is a set of indexed elements. It can be conceptualized as follows:

Arrays

Usually, the indexing starts at 0 and in code they are represented as a comma separated list enclosed by square brackets :

array = [ element0, element1, element2, element3, . . ., elementn ]

To refer to an element of the array, you use the name of the array and the square brackets indicating the index:

array[ index ]

Depending on the language the elements will be all of the same type (integer, characters, booleans, objects, etc.) or not, allowing each element to be different from the others.

A matrix is nothing more than an array of arrays (in the case of a bidimensional matrix):

Matrices

In the image above, we have an array of m elements, in which each element is an array of n elements, giving us a matrix of m x n elements in total.

This ones will be represented in code as a comma separated list of arrays:

matrix = [ 
           [ element00, element01, element02, ..., element0n ],
           [ element10, element11, element12, ..., element1n ],
           [ element20, element21, element22, ..., element2n ],
           . . .
           [ elementm0, elementm1, elementm2, ..., elementmn ]
         ]

And you access the elements using double square brackets! The first one referring to the big array, the second one referring to the element within the small array:

matrix[ indexm ][ indexn ]

As you can imagine, we can have also matrices of more than two dimensions:

Cube

And this in code is represented as an array, with elements that are also arrays, with elements that are also arrays…

cube = [
         [ [], [], [], . . ., [] ],
         [ [], [], [], . . ., [] ],
         [ [], [], [], . . ., [] ],
         [ [], [], [], . . ., [] ],
         . . .,
         [ [], [], [], . . ., [] ],
       ]

You use three square brackets to give the coordinates for your desired element:

cube[ indexm ][ indexn ][ indexk ]

This type of representation (easier to imagine as a cube) is quite useful when you have to keep the status of a matrix over different times. I recommend the article in Wikipedia about Data Cubes, is quite good.

Second part, I have a matrix, now what?

Let’s start with bidimensional matrices. The calculations that exist for an algebraic matrix (addition, multiplication, normalization) can be applied also to this matrices, take the link to Wikipedia at the top of the article to get to know more about this.

In algebra there’s the concept of matrix rotation, which makes sense in euclidean spaces (coordinate system change, base change, etc) but what about a physical, literal rotation of the elements in the matrix?

Clockwise rotation

If we want this:

Rotation

To be able to create a matrix in which the elements changed their position rotating clockwise or counterclockwise respecting the original one.

We will start our analysis with a 3×3 matrix, named A:

0, 1, 2
3, 4, 5
6, 7, 8

That will be rotated clockwise resulting in this 3×3 matrix, named B:

6, 3, 0
7, 4, 1
8, 5, 2

The strategy to follow is to define the relationship between the positions in the starting matrix A and the final one B, so we can assign the new values in B based on this:

B[ i ][ j ] = A[ rotate i ][ rotate j ] 
    for all i in the rows, 
    for all j in the columns

If we check all the elements in the starting and final matrices the assignation looks like this:

First row:
    B[0][0] : A[2][0]
    B[0][1] : A[1][0]
    B[0][2] : A[0][0]

Second row:
    B[1][0] : A[2][1]
    B[1][1] : A[1][1]
    B[1][2] : A[0][1]

Third row:
    B[2][0] : A[2][2]
    B[2][1] : A[1][2]
    B[2][2] : A[0][2]

The next logical step is to find a function to calculate which value should be taken given a coordinate in the matrices, so we don’t have to care about the size of the matrix.

Let’s review the first row of the rotated matrix:

First row:
    B[0][0] : A[2][0]
    B[0][1] : A[1][0]
    B[0][2] : A[0][0]

The way we read this is

  • The element in A[2][0] is going to be located in B[0][0]
  • The element in A[1][0] is going to be moved to B[0][1]
  • And the element in A[0][0] will be located in B[0][2].

If we notice, the j indexes in the matrix B start in the lowest possible value (0) and increase while we advance, opposite to the i indexes in matrix A, they start in the highest possible value (2 for a 3×3 matrix) and will decrease while we advance.

We can say that the j indexes in B are the inverse of the i indexes in the A matrix.

On the other hand, the i indexes in matrix B never change (because we are working on one row), just as the j indexes in matrix A. In a sort of way the first row in B becomes the transpose of the first column in A then reversing the order of the elements.

So, if we apply the constraints for the indexes, it seems that B[ i ][ j ] will receive the value in A[ inverse of j ][ i ].

A way to calculate the inverse of a number in a range is to take the maximum value (n) and subtract the number from it:

n - number = inverse
number + inverse = n

The above rule satisfies the closure on the integer numbers (which happens to be a subset of the real numbers).

This apply for ranges [1,n] so if we want to do it in programming way [0, n-1] the inverse calculation changes as follows:

(n - 1) - number = inverse

So the function defined above, including our analysis goes as follows:

B[ i ][ j ] = A[ (n-1)-j  ][ i ] 
    for all i in the rows, 
    for all j in the columns

Note that n in this case, corresponds to the number of columns (since we are operating with the j indexes).

Let’s test for the second and third rows:

Second row:
    B[1][0] : A[n-j-1][i] : A[3-0-1][1] : A[2][1]
    B[1][1] : A[n-j-1][i] : A[3-1-1][1] : A[1][1]
    B[1][2] : A[n-j-1][i] : A[3-2-1][1] : A[0][1]

Third row:
    B[2][0] : A[n-j-1][i] : A[3-0-1][2] : A[2][2]
    B[2][1] : A[n-j-1][i] : A[3-1-1][2] : A[1][2]
    B[2][2] : A[n-j-1][i] : A[3-2-1][2] : A[0][2]

If the matrix is not square (mxn, m != n), the function will be the same with the difference that the resulting matrix will have different dimensions than the original:

Rotation MxN

Counterclockwise

For the counterclockwise rotation, these are our matrices:

A:
  0, 1, 2
  3, 4, 5
  6, 7, 8

B:
  2, 5, 8
  1, 4, 7
  6, 7, 8

So, if we follow the same exercise we did for clockwise operations we have that for the first row:

First row:
    B[0][0] = A[0][2]
    B[0][1] = A[1][2]
    B[0][2] = A[2][2]

So it seems, that the j indexes in matrix B are exactly the same as i indexes in matrix A, while i indexes in B are the inverse (zero based) of the j indexes in A.

Given that, our function goes as follows:

B[ i ][ j ] = A[ i ][ m-i-1 ] 
    for all i in the rows, 
    for all j in the columns

Note that m in this case, corresponds to the number of rows (since we are operating with the i indexes).

Double rotation / Reflection

If we want to perform a double rotation we could do a clockwise rotation twice or a counterclockwise rotation twice as well, it wouldn’t matter which direction we take since both will get the same.

This movement can also be considered the reflection of the matrix over the right diagonal (the left one is the one used to transpose the matrix):

Double Rotation / Reflection

But if we think for a second, we can also find a function to apply the double rotation / reflection in one step to save processing.

Let’s start with our two same matrices:

A:
  0, 1, 2
  3, 4, 5
  6, 7, 8

B:
  8, 7, 6
  5, 4, 3
  2, 1, 0

And as we did before, let’s analyze the first row:

First row: 
    B[0][0] = A[2][2]
    B[0][1] = A[2][1]
    B[0][2] = A[2][0]

If we pay attention, the i indexes are the inverse of j ones… in both matrices!!

B[0][2] = A[2][0], where 0 is the inverse of 2 and viceversa

So if we apply inverse for both indexes, our formula changes as follows:

B[ i ][ j ] = A[ n-j-1 ][ m-i-1 ] 
    for all i in the rows, 
    for all j in the columns

Note that m in this case corresponds to the number of rows (since we are operating with the i indexes) while n corresponds to the number of columns (for the operations with j indexes).

Third, conclusion and more to come…

Given a matrix A with dimensions m x n (m can possibly be equals to n), the rotated matrix (named B) is defined as follows:

For clockwise rotation:

B[ i ][ j ] = A[ n-j-1 ][ i ] 
    for all i in the rows, 
    for all j in the columns
    n being the number of columns

For counterclockwise rotation:

B[ i ][ j ] = A[ j ][ m-i-1 ] 
    for all i in the rows, 
    for all j in the columns
    m being the number of rows

And for double rotation or reflection:

B[ i ][ j ] = A[ n-j-1 ][ m-i-1 ] 
    for all i in the rows, 
    for all j in the columns
    n being the number of columns
    m being the number of rows

But what about cubes? Well… Stay tuned because I plan to write an article about rotation in cubes (like a rubik cube for instance). The idea is to reorganize the data by rotating it, keeping the indexed integrity.

In another topic still related, within the realm of scientific computing, large matrix operations is a common challenge, I plan to write another article about this and discuss some possible approaches to solve this.

Questions, comments, suggestions, don’t hesitate to add them below😉