I'm writing a computer code to solve a problem, and I ran into some difficulties. This is not a coding question, my problem is purely mathematical, I will explain.
We have a matrix $M\in Mat(\mathbb R)_{n\times n}$ such that the first 2 diagonals have non zero values as entries, and everything else is zero.
We fill the upper half of the matrix except for the 2 given diagonals (meaning $i+2\leq j$) with the following formula:
$M_{i,j}=\max(a+\min(M_{i+2,j},M_{i+1,j-1}), b+\min(M_{i+1,j-1},M_{i,j-2}))$
where $a,b$ are some given numbers. You can see that in order to compute the $k$th diagonal, we need to have the $k-2$ diagonal. Since we were given the first $2$, we can fill the upper half of the matrix. This results in an upper triangular matrix.
Now, for reasons of computer science and conserving memory, I don't want to allocate an entire matrix. Think of each of these entries as something you pay for. In the above notation, we paid for $n^2$ entries but used only half.
So to solve this, I defined a new matrix. Such that the first row has $n$ entries, the second row has $n-1$, and so on. Generally speaking, the $i$th row has $n-i$ elements. In computer science this is called a jagged array.
But since we changed the dimensions of the matrix, the formula has to change as well. We essentially moved every element $i$ columns to the left ($i$ starts at zero.). So we should have $M_{i,j}=M'_{i,j-i}$ where $M'$ is the new jagged array, and so the formula above will become:
$M'_{i,j}=\max(a+\min(M'_{i+2,j-i},M'_{i+1,j-1-i}), b+\min(M'_{i+1,j-1-i},M'_{i,j-2-i}))$
But for some reason, this formula does not work. I'll show an example. Suppose we have $a=47$ and $b=26$ and:
$M=\begin{pmatrix}47 & 47 & x\\0 & 45 & 45 \\0 & 0 & 26\end{pmatrix}$ And we want to find $x$ using the formula above for non jagged matrices:
$x=M_{0,2}=\max(47+\min(M_{2,2},M_{1,1}),26+\min(M_{1,1},M_{0,0}))=\max(47+\min(26,45),26+\min(26,47))=\max(47+26,26+26)=47+26=73$
So $x=73$. But you will see now that if we do this with a jagged array, the jagged array formula will not work. To create the jagged array, we will shift the entries of row $i$, $i$ columns to the left:
$M'=\begin{pmatrix}47 & 47 & x\\45 & 45 \\26\end{pmatrix}$.
We want to calculate $x$ with the jagged array formula: $x=M'_{0,2}=\max(47+\min(M'_{2,2},M'_{1,1}),26+\min(M'_{1,1},M'_{0,0}))$
But the entry $M'_{2,2}$ does not exist! So our formula after the change to smaller matrix dimensions was incorrect!
I need help fixing the formula please, I don't know where is the mistake.