Linear algebra on tiled grids

After introducing grids and linear algebra, it is time to merge both subjects into a single one: what can we say about linear algebra when we look at regular grids?

To start, let’s consider the regular square grid. Consider the following grid:

How do we get from the green square to the red one? It’s simple, we move 3 squares to the right and three squares up. Besides defining the classical taxi-cab (Manhattan) distance, this also defines a vector basis for this 2D space:

If we use \(\mathbf{e_1}\) for the horizontal red vector and \(\mathbf{e_2}\) for the vertical green one and \(\mathbf{x}\) for the relative vector between the green and red square we have:

\[\mathbf{x} = 3\mathbf{e_1} + 3\mathbf{e_2}\]

which describes that we need to move 3 times in the \(\mathbf{e_1}\) direction and 3 times in the \(\mathbf{e_2}\) one.

So far, all is simple and trivial. But this is not the only base we could use. Consider this other image:

Now, the movement set is a down diagonal vector (let’s call it \(\mathbf{e_1'}\)) and a knights-move up diagonal vector (let’s call it \(\mathbf{e_2'}\)). We only need one down diagonal vector and 2 knights-move one to go from the green square to the red one:

\[\mathbf{x} = \mathbf{e_1'} + 2\mathbf{e_2'}\]

The same vector has been written in two separate bases as two different sums.

Next, let’s look at a hexagonal grid:

Can we use the same concepts to describe the movement from the green tile to the red one? Of course we can: first, pick two vectors and then add combinations of them to get the desired displacement. We could do like in this image:

Let’s use \(\mathbf{b_1}\) for the red vector and \(\mathbf{b_2}\) for the green one (to mimic the square example, but using \(\mathbf{b}\) instead of \(\mathbf{e}\)). Then:

\[\mathbf{x} = 3\mathbf{b_1} + 4\mathbf{b_2}\]

But this is not the only option for the starting vectors. We could have picked these ones:

Using the same convention as in the square grid, we now have:

\[\mathbf{x} = -\mathbf{b_1'} + 4\mathbf{b_2'}\]

Here, we had to flip \(\mathbf{b_1'}\), so it’s multiplier is negative.

At this point, you should be convinced that the same vector (\(\mathbf{x}\)) could be expressed differently, depending on what basis we pick. You should also be convinced that we always need 2 vectors. Using just one vector would make it impossible to represent displacements from most tiles to most tiles. Adding a third vector might simplify some expressions (e.g., imagine if in the last image we also added a vertical vector), but we can always express this third vector as a sum of scaled versions of the other two.

The fact that we always need 2 vectors is due to the fact that the grids are all embedded in 2D space. In a future article I’ll introduce grids in 3D space. But, for this article we still have another question to answer: if the expression for the displacement vector depends on the basis we pick, is there a “better” base than the others?

Well, it depends on the problem, convention, and the fact that basis vectors that are orthogonal (at \(90^\circ\) angles) are usually better. For the square grid, we can pick orthogonal vectors, the \(\mathbf{e_1}\) and \(\mathbf{e_2}\) we used in the first example. But, for the hexagonal grid, picking orthogonal vectors would introduce irrational numbers in the sums, making the expressions more complicated.

Next, if one basis is better suited that other for one problem, how do we convert between the bases? How would we go, for example, from the sum expressed in \(\mathbf{b_i}\) to the sum expressed in \(\mathbf{b_i'}\)? It’s simple: just write the new basis vectors as sums of the old ones and rewrite:

\[\mathbf{b_1'} = \mathbf{b_1}\]

\[\mathbf{b_2'} = \mathbf{b_1} + \mathbf{b_2}\]

So:

\[\mathbf{x} = -\mathbf{b_1'} + 4\mathbf{b_2'}\]

becomes

\[\mathbf{x} = -\mathbf{b_1} + 4\left(\mathbf{b_1} + \mathbf{b_2}\right)\]

which is the original

\[\mathbf{x} = 3\mathbf{b_1} + 4\mathbf{b_2}\]

In a future article I’ll introduce a way to describe all of these relations in a simple, concise, form. As a spoiler: it will be matrix multiplication.