Rows and columns

A programmer occasionally ends up in a situation where his program almost works. There is something slightly off with the program. One of the values is just one unit away from the desired value.

At this point, the programmer gets cocky and starts to shotgun-program. This is where they change something quickly, without thinking about it, and hope that that solves it. They add a '+1' here and a '-1' there, in the hope that after this, they will never have to look at that piece of code again.

Off-by-one hell

After a few such attempts, the programmer ends up in what is known as off-by-one hell. This particular side of hell can only be gotten out of by stepping back, looking at the problem again, preferably on a whiteboard.

Off-by-one hell can be caused by a few kinds of problems, one of which is working with matrices and their indexes. This post is meant as a big cheat-sheet for this particular kind of problem.

The matrix

First things first. You have to name the matrix.

  • I will call it $A$.
  • $A$ is an $m$ by $n$ matrix. ('m' comes first in the alphabet.)
  • $m \times n$ means that $A$ has $m$ rows and $n$ columns.
  • An element $a_{i,j}$ of $A$ is on the $i$-th row and $j$-th column.
  • $A$ is indexed in a zero-based manner. (In programming this is usually the case. In mathematics this doesn't matter.)

$$ A = \begin{pmatrix} a_{0,0} & a_{0,1} & a_{0,2} & \cdots & a_{0,n-1}\ a_{1,0} & a_{1,1} & a_{1,2} & \cdots & a_{1,n-1}\ a_{2,0} & a_{2,1} & a_{2,2} & \cdots & a_{1,n-1}\ \vdots & \vdots & \vdots & \ddots & \vdots\ a_{m-1,0} & a_{m-1,1} & a_{m-1,2} & \cdots & a_{m-1,n-1}\ \end{pmatrix} $$

Storing the matrix.

The matrix can be stored in at least four ways.

  • As a two-dimensional matrix in row-major order: $a_{i,j}$ is accessed as a[i][j].
  • As a two-dimensional matrix in column-major order $a_{i,j}$ is accessed as a[j][i].
  • As a one-dimensional array in row-major order: $a_{i,j}$ is accessed as a[i*m+j].

$$ A = \begin{pmatrix} a[0] & a[1] & a[2] & & a[n-1]\ a[n] & a[n+1] & a[n+2] & \cdots & a[n+(n-1)]\ a[2n] & a[2n+1] & a[2n+2] & \cdots & a[2n+(n-1)]\ \vdots & \vdots & \vdots & \ddots & \vdots\ a[(m-1)n] & a[(m-1)n+1] & a[(m-1)n+2] & \cdots & a[(m-1)n+n-1]\ \end{pmatrix} $$

  • As a one-dimensional array in column-major order: $a_{i,j}$ is accessed as a[i+j*n].

$$ A = \begin{pmatrix} a[0] & a[m] & a[2m] & \cdots & a[(n-1)m]\ a[1] & a[m+1] & a[2m+1] & \cdots & a[(n-1)m +1]\ a[2] & a[m+2] & a[2m+2] & \cdots & a[(n-1)m +2]\ \vdots & \vdots & \vdots & \ddots & \vdots\ a[m-1] & a[m+(m-1)] & a[2m+(m-1)] & \cdots & a[(n-1)m-m-1]\ \end{pmatrix} $$

As a rule of thumb, I recommend using the first option if you have a choice.

Variables

Often we want to iterate over the matrix. In imperative languages, we need at least one variable and a loop for this. To note:

  • The amount of rows is $m$ but the row-length is $n$.
  • The amount of columns is $n$ but the column-length is $m$.

Once we've used good variable names, this becomes rather easy.

for (int row = 0; row < m; row++)
    for (int column = 0; column < n; column++)
        a[row][column];

Reverse indexing.

Suppose we're given the index of an element in the matrix, how do we retrieve the row and the column number? This depends on the way the matrix is stored, of course. At this point it is very important that you've used a zero-based system of indices. Otherwise you'll just end up in another part of off-by-one hell. Suppose you have an index of a value. We can then iterate over the matrix with one for-loop, even if it is stored as a two-dimensional array.

  • row-major order: row = index / n and column = index % n
for (int index = 0; index < m*n; index++)
        a[index / n][index % n];
  • column-major order: row = index / m and column = index % m or
for (int index = 0; index < m*n; index++)
        a[index / m][index % m];

If you liked this blog post, please consider becoming a supporter:

Become A Supporter