Rectangular representation for matrix diagonal

I'm doing dynamic time warping and need to represent the anti-diagonal of a square matrix compactly (cache efficiently) as 2D array.

I need functions to map indices of one matrix to the other (in both directions).

I need functions to map deltas both ways.

Lets call the matrix whose anti-diagonal we are interested in the matrix Mat (using (y,x) for coordinates) and the 2D array representation of the anti-diagonal the Rep (using (j,i) for indices).

I will assume the inner dimension of Rep is even of length 2*m.

We can index the diagonals such the adding coordinates gives us the index.

diag = (y, x) ↦ y + x

And that corresponds to the index j of the outer dimension of Rep

We want to find the psudo-inverse of diag that maps back to the start coordinate of the diagonal. Let us break down pinvdiag a linear term (a function of d) and a constant term (function of m)

There are two possibilities for the linear f term

d ↦ (d / 2,(d + 1) / 2)
d ↦ ((d + 1) / 2, d / 2)
# or equivalently
d ↦ [(d + first(f(1))) / 2, (d + second(f(1))) / 2]

Now let us find the constant

⊞(⊂:) (- 5 ⇡7) ⇌(⇡7)
╭─                                        
╷ 6,¯5  6,¯4  6,¯3  6,¯2  6,¯1  6,0  6,1  
╷ 5,¯5  5,¯4  5,¯3  5,¯2  5,¯1  5,0  5,1  
  4,¯5  4,¯4  4,¯3  4,¯2  4,¯1  4,0  4,1  
  3,¯5  3,¯4  3,¯3  3,¯2  3,¯1  3,0  3,1  
  2,¯5  2,¯4  2,¯3  2,¯2  2,¯1  2,0  2,1  
  1,¯5  1,¯4  1,¯3  1,¯2  1,¯1  1,0  1,1  
  0,¯5  0,¯4  0,¯3  0,¯2  0,¯1  0,0  0,1  
                                         ╯

Let f be the linear term.

• If f(1) = 0,1 then constant = (m, -m)
• If f(1) = 1,0 then constant = (m-1, 1-m).
• or equivalently constant = (m-first(f(1)), first(f(1))-m).

Therefore

pinvdiag = d ↦ (d/2,(d+1)/2) + (m, -m)
pinvdiag = d ↦ ((d+1)/2,d/2) + (m-1, 1-m)

So we have

Mat2Rep = (y, x) ↦ (y + x, x - second(pinvdiag(d)))
Rep2Mat = (j, i) ↦ pinvdiag(j) + (-i, i)

Deltas

let delta be the function that maps (dy, dx) ↦ (dj, di).

Let ust try to derive delta(-1,0) i.e. a down step. Let d be the diagonal index of the starting point of the delta.

• If d % 2 == first(f(1)) we have delta(-1, 0) = (dj=-1, di=0) otherwise (dj=-1, di=1)

For the dd even parity case. delta = (dy,dx) ↦ [dy + dx, (dx - dy) / 2]

Given these two facts, lets guess that

delta = (dy,dx), (y0, x0) ↦ [
         dy + dx, 
         (dx - dy) / 2 + (y0 + x0 + first(f(1))) % 2
      ]

To avoid a extra addition you can chose f(1)=(0, 1) rather than f(1)=(1, 0)