the matrix rollup theorem
DOCX · 22.7 KB
Open DOCX file
Short note by Phil dated 11.18.10 on solving a system of equations with lower-triangular coefficients plus one upper off-diagonal. It states a theorem expressing x_n as (-1)^n x0 det A_n divided by the product of the superdiagonal entries, and checks it by hand for x1 through x3. He compares it with a simple recursive loop in Maple and sketches an induction proof via row operations, leaving it unfinished.
AI-written summary; may contain errors.
Extracted text (machine-read; may contain errors)
The Matrix Rollup Problem PhL 11.18.10
Suppose you have a system of equations like this
a00x0 + a01x1 = 0
a10x0 + a11x1 + a12x2 = 0
a20x0 + a21x1 + a22x2 + a23x3 = 0
a30x0 + a31x1 + a32x2 + a33x3 + a34x4 = 0
.......
Define these matrices and notice how each gives an equation above
A2 = = (-1/a12)
A3 = = (-1/a23)
A4 = etc
Theorem: The solution to this infinite system of equations can be written this way
xn = (-1)n x0 detAn / (a01 a12 a23 ..... an-1,n)
= (-1)n x0 detAn / Πi=0n-1(ai,i+1)
So this is just a fancy way to "do the rollup". But in my Maple world, it would be more work to compute all these determinants that to just do the rollup in code like this
for n = 1 to 10 do
xn = (-1/an-1,n) [an-1,0x0 + an-1,1x1 + .... an-1,n-1xn-1]
for n = 1 to 10 do
x[n] = (-1/an-1,n) [ Σk=0n-1an-1,k x[k] ]
I fiddle with this theorem below but did not do the required induction proof.
One idea: Notice that
detA3 = a22 det A2 - a12 det A2(1x→2x)
detA4 = a34 det A3 - a23 det A3(2x→3x)
where 1x→2x means replace A1x by A2x for all x.
Meanwhile,
detA3 = εijka0ia1ja2k
detA3(2x→3x) = εijka0ia1ja3k = a3k
So
detA4 = a34 εijka0ia1ja2k - a23 εijka0ia1ja3k
The matrices are triangular plus one upper off diagonal.
We know we can "roll things up" in this way
x1 = (-1/a01) a00 x0
x2 = (-1/a12) [a10x0 + a11x1] = (-1/a12) [a10x0 + a11{(-1/a01) a00 x0}]
= (-1/a12) (-1/a01)[ a10(-a01) + a11 a00] x0 = (-1/a12) (-1/a01) detA2x0
x3 = (-1/a23) [a20x0 + a21x1 + a22x2]
= (-1/a23) [a20x0 + a21{ (-1/a01) a00 x0} + a22{(-1/a12) (-1/a01) detA2}x0]
= (-1/a23) (-1/a12) (-1/a01) [(-a12) (-a01)a20x0 + (-a12)a21{ a00 x0} + a22{ detA2}x0]
= (-1/a23) (-1/a12) (-1/a01) [(-a12) (-a01)a20 + (-a12)a21{ a00 } + a22{ detA2}] x0
= (-1/a23) (-1/a12) (-1/a01) [(-a12) [ a00a21- a01a20] + a22{ detA2}] x0
= (-1/a23) (-1/a12) (-1/a01) detA3 x0
We can see the pattern and we could do an induction proof, but here is the pattern
x1 = (-1/a01)detA1x0
x2 =(-1/a01) (-1/a12) detA2x0
x3 = (-1/a01) (-1/a12) (-1/a23) detA3 x0
x4 = (-1/a01) (-1/a12) (-1/a23) (-1/a34) detA4 x0
....
xn = (-1)n detAn / (a01 a12 a23 ..... an-1,n)x0
Rewrite as
x1/x0 = (-1)1 detA1 / (a01)
x2/x0 = (-1)2 detA2 / (a01 a12)
x3/x0 = (-1)3 detA3 / (a01 a12 a23)
x4/x0 = (-1)4 detA4 / (a01 a12 a23 a34)
...
xn/x0 = (-1)n detAn / (a01 a12 a23 ..... an-1,n)
The start of the induction would be
xk/x0 = (-1)k detAk / (a01 a12 a23 ..... ak-1,k)
The equation of interest is
ak0x0 + ak1x1 + ak2x2 + ak3x3 + ak4x4 + ... + ak,k+1 xk+1= 0
xk+1/x0 = (-1/ak,k+1) [ak0 + ak1x1/x0 + ak2x2/x0 + ak3x3/x0 + ak4x4/x0 + ak-1,k xk/x0]
= (-1) [ak0 + ak1x1/x0 + ak2x2/x0 + ak3x3/x0 + ak4x4/x0 + ak-1,k xk/x0]/ak,k+1
= (-1) [ ak0 + ak1 (-1)1 detA1 / (a01) + ak2(-1)2 detA2 / (a01 a12)
+ ak3 (-1)3 detA3 / (a01 a12 a23) +
.. + ak-1,k(-1)k detAk / (a01 a12 a23 ..... ak-1,k) ] /ak,k+1
we need some supporting theorem which says
(-1)k+1 detAk+1 / (a01 a12 a23 ..... ak,k+1)
= (-1) [ ak0 + ak1 (-1)1 detA1 / (a01) + ak2(-1)2 detA2 / (a01 a12)
+ ak3 (-1)3 detA3 / (a01 a12 a23) +
.. + ak-1,k(-1)k detAk / (a01 a12 a23 ..... ak-1,k) ] /ak,k+1
or
(-1)k detAk+1 / (a01 a12 a23 ..... ak,k+1)
= [ ak0 + ak1 (-1)1 detA1 / (a01) + ak2(-1)2 detA2 / (a01 a12)
+ ak3 (-1)3 detA3 / (a01 a12 a23) +
.. + ak-1,k(-1)k detAk / (a01 a12 a23 ..... ak-1,k) ] /ak,k+1
or
detAk+1
= [ ak0 (a01 a12 a23 ..... ak,k+1)
+ ak1 (-1)k-1 detA1 ( a12 a23 ..... ak,k+1)
+ ak2(-1)k-2 detA2 ( a23 ..... ak,k+1)
+ ak3 (-1)k-3 detA3 ( a34 . ak,k+1)
+ ....
+ ak-2,k-1 (-1)1 detAk-1 (ak,k+1)
+ ak-1,kdetAk
So the secret to this induction proof is showing this decomposition of the determinant for a matrix of this nearly triangular form.
Ah yes. I think you use those row operations which preserve the determinant!
Theorem 2D: Add a multiple of one row to another, det does not change.
So start with detA4 and our picture above. Multiply third row by -a34/a23 and add to 4th row to get
You just keep doing this.
OK, enough fiddling on this. I could do it if I had to. I wonder if this little theorem has a name or some kind of handle people use to talk about it. Here is the theorem