Confusing matrix generation example in Lua

Question

If you want to create NxM matrix in Lua you basically do the following:

function get_zero_matrix(rows, cols)
  matrix = {}
  for i=1, rows do
    matrix[i] = {}
    for j=1, cols do
      matrix[i][j] = 0
    end
  end
  return matrix
end

However, on the official Lua website I've seen the second variant:

function get_zero_matrix2(rows, cols)
  mt = {}
  for i=1, rows do
    for j=1, cols do
      mt[i*cols + j] = 0
    end
  end
  return mt
end

First, I don't understand how it works. How [i*M + j] index is supposed to create rows and columns? Second, I tried this variant, it works but what it returns is actually an array, not NxM matrix:

M = function get_zero_matrix2(10, 20)
print(#M, #M[1])

> attempt to get length of a nil value (field '?')

Can you please explain how the second variant works? Maybe I am misinterpreting it.

Answer 1

I don't understand how it works.

For a 2D array of dimension N (rows) x M (cols), the total number of required elements = N * M. Now creating N * M elements in one shot as a single array, we will essentially have a 1D array (flattened 2D array) in memory. Since the formula assumes array index start as 0 and not 1 (the usual Lua's convention), we'll follow 0: the first M items with indices [0, M - 1] form row 0, next M items with indices [M, 2M - 1] form row 1, and so on.

Memory layout for a 5 x 2 array; index 4 in this 1D array is (2, 0) in the 2D array.

   --+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+--
 ... | 0,0 | 0,1 | 1,0 | 1,1 | 2,0 | 2,1 | 3,0 | 3,1 | 4,0 | 4,1 | ...
   --+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+--

     |-- row 0 --|-- row 1 --|-- row 2 --|-- row 3 --|-- row 4 --|

To access element (i, j), one would get past i - 1 rows and then access the j^th item on the i^th row. But the index is already one lesser, since the index starts at 0, so i can be used as-is. Thus i * rows + j gives the right index.

How [i*M + j] index is supposed to create rows and columns?

It doesn't. It's an abstraction over a 1D array of numbers, giving the interface of a matrix. In languages like C, declaring a 2D array, most implementations do something similar. int a[2][3] would create an array of 6 integers and do the indexing with the formula above, so this is not an uncommon pattern.

Answer 2

The variant available on Lua PiL is actually representation/mapping of a 2D array as a 1D array.

Basically, consider the following 2x3 array/matrix:

{
    {11, 12, 13},
    {21, 22, 23}
}

The variant, instead creates it as:

{
    [4] = 11,
    [5] = 12,
    .
    .
    .
    [9] = 23
}

Now, when you want to, let's say, get matrix[1][x], you'll instead fetch:

matrix[1 * rows + x]

It does not, in any way create rows and columns. It is just data stored in a single row of numbers. You will have to implement your own logic; which here, essentially; is i * M + j.

---

The i*M + j is usually seen in languages with 0-indexing array, like C, where the matrix would be:

{
    [0] = 11,
    [1] = 12,
    [2] = 13,
    .
    .
    .
    [5] = 23
}