**Contents:**

Gauss-Jordan Solution of "n x n" Linear Equations

Don Lancaster Synergetics, Box 809, Thatcher, AZ 85552 copyright c2007 as GuruGram #77 http://www.tinaja.com don@tinaja.com (928) 428-4073

Gaussian Elimination is the process of initially playing around with some array

values ahead to time to greatly simplify the final solution to a large class of " n x n" linear equations. While a Jordan Further Processing often can greatly simplify any automated computer programming. Presented here is a tutorial on Gauss-Jordan theory. Along with some remarkably simple and powerful JavaScript routines for your own Gauss-Jordan solutions. Applications include everything from Digital Filters to Magic Sinewaves. Actual working code can be extracted from here. Consider five linear equations in five unknowns...

A0*v A1*v A2*v A3*v A4*v + + + + + B0*w B1*w B2*w B3*w B4*w + + + + + C0*x C1*x C2*x C3*x C4*x +D0*y +D1*y +D2*y +D3*y +D4*y + + + + + E0*z E1*z E2*z E3*z E4*z = = = = = K0 K1 K2 K3 K4

While all sorts of solution methods exist, we seek one that is computationally efficient. If we dink around with some manipulations ahead of time, we can eventually end up with a solution that will be obvious by inspection! Arrange the coefficients into a group of arrays...

[ [ [ [ [ A0 A1 A2 A3 A4 B0 B1 B2 B3 B4 C0 C1 C2 C3 C4 D0 D1 D2 D3 D4 E0 E1 E2 E3 E4 K0 K1 K2 K3 K4 ] ] ] ] ]

The rules for our "Gauss" part of rearrangement are that any row can be scaled by any constant term by term without changing the results. And that any row can be subtracted from any other row term by term and substituted. Again without changing the results.

-- 76 . 1 --

In interests of sanity, let "~" be any coefficient that resulted from any and all previous manipulation. Scale the top row by dividing by its initial value...

[ [ [ [ [ 1 A1 A2 A3 A4 ~ B1 B2 B3 B4 ~ C1 C2 C3 C4 ~ D1 D2 D3 D4 ~ E1 E2 E3 E4 ~ K1 K2 K3 K4 ] ] ] ] ]

Scale the top row by A1 and subtract it from the next row down and replacing...

[ [ [ [ [ 1 0 A2 A3 A4 ~ ~ B2 B3 B4 ~ ~ C2 C3 C4 ~ ~ D2 D3 D4 ~ ~ E2 E3 E4 ~ ~ K2 K3 K4 ] ] ] ] ]

Similarly, scale the top row by A2 and subtract it from the middle row. Then scale by A3 for row 3 and A4 for row4...

[ [ [ [ [ 1 0 0 0 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ] ] ] ] ]

Now, scale the second row down by its first nonzero coefficient...

[ [ [ [ [ 1 0 0 0 0 ~ 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ] ] ] ] ]

Next, force zeros in the second column the same as we did with the first, but using the second row for subtraction and substitution...

[ [ [ [ [ 1 0 0 0 0 ~ 1 0 0 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ] ] ] ] ]

Keep working your way through the array, this time scaling the third row down by its first nonzero term and then using scaled subtractions to zero out everything below in the same column. Eventually, you should end up with...

-- 76 . 2 --

[ [ [ [ [

1 0 0 0 0

~ 1 0 0 0

~ ~ 1 0 0

~ ~ ~ 1 0

~ ~ ~ ~ 1

~ ~ ~ ~ ~

] ] ] ] ]

This completes the Gauss part of the process. The lower right squiggle will be z by inspection! Relabel the above array...

[ [ [ [ [ 1 0 0 0 0 c01 c02 c03 c04 j05 ] 1 c12 c13 c14 j15 ] 0 1 c23 c24 j25 ] 0 0 1 c34 j35 ] 0 0 0 1 z ]

where cxx is the row and column coefficient for the left side equation terms, and jxx is the similar row and column coefficient for the right side equation term. The traditional way to solve this was by back substitution. You can start off with y = j35 - z*c34 and so on. And then work your way up a row at a time, making more complex calculations until you have v through z all solved. The Jordan approach starts off the same way, but it works one column at a time, greatly simplifying computer programming. Especially when more than one n x n equation set size is to be accommodated. The new rule is that any constant can

be subtracted from one term in the left side of the equation as long as that same constant get subtracted from the right side of the equation.

Subtract z*c34 from row 4...

[ [ [ [ [ 1 0 0 0 0 c01 c02 c03 c04 j05 ] 1 c12 c13 c14 j15 ] 0 1 c23 c24 j25 ] 0 0 1 0 y ] 0 0 0 1 z ]

So far, this is the same as the usual back substitution. We now can observe y by inspection The difference with Jordan is to continue by working columns instead of rows. Modify the rows by subtracting z*c24, z*c14, and z*c04 to get...

[ [ [ [ [ 1 0 0 0 0 c01 c02 c03 1 c12 c13 0 1 c23 0 0 1 0 0 0 0 0 0 0 1 ~ ] ~ ] ~ ] y ] z ]

-- 76 . 3 --

Next, modify column three by subtracting y*c23, y*c13, and y*c03. And then column two by subtracting x*c12 and x*c02. And finally column one by subtracting w*c01 to get...

[ [ [ [ [ 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 v] w] x] y] z]

Your values v through z are now instantly readable by inspection! Once again, the Jordan method takes just as many calculations as does a back substitution, but it greatly simplifies computation. In that loops do not have any multiple calculations or complicated cross-coefficients in them. This is especially handy when it comes to making the code n independent.

A Code Example

Here's a JavaScript program that solves n x n linear equations. It is amazingly compact, offers 64 bit arithmetic, and works for most any sane value of n. But it does not trap any div0's or handle wild coefficients. Per this main proc...

function solveGaussJordan() { gjNsize = eqns.length ; for (var iii = 0; iii

Don Lancaster Synergetics, Box 809, Thatcher, AZ 85552 copyright c2007 as GuruGram #77 http://www.tinaja.com don@tinaja.com (928) 428-4073

Gaussian Elimination is the process of initially playing around with some array

values ahead to time to greatly simplify the final solution to a large class of " n x n" linear equations. While a Jordan Further Processing often can greatly simplify any automated computer programming. Presented here is a tutorial on Gauss-Jordan theory. Along with some remarkably simple and powerful JavaScript routines for your own Gauss-Jordan solutions. Applications include everything from Digital Filters to Magic Sinewaves. Actual working code can be extracted from here. Consider five linear equations in five unknowns...

A0*v A1*v A2*v A3*v A4*v + + + + + B0*w B1*w B2*w B3*w B4*w + + + + + C0*x C1*x C2*x C3*x C4*x +D0*y +D1*y +D2*y +D3*y +D4*y + + + + + E0*z E1*z E2*z E3*z E4*z = = = = = K0 K1 K2 K3 K4

While all sorts of solution methods exist, we seek one that is computationally efficient. If we dink around with some manipulations ahead of time, we can eventually end up with a solution that will be obvious by inspection! Arrange the coefficients into a group of arrays...

[ [ [ [ [ A0 A1 A2 A3 A4 B0 B1 B2 B3 B4 C0 C1 C2 C3 C4 D0 D1 D2 D3 D4 E0 E1 E2 E3 E4 K0 K1 K2 K3 K4 ] ] ] ] ]

The rules for our "Gauss" part of rearrangement are that any row can be scaled by any constant term by term without changing the results. And that any row can be subtracted from any other row term by term and substituted. Again without changing the results.

-- 76 . 1 --

In interests of sanity, let "~" be any coefficient that resulted from any and all previous manipulation. Scale the top row by dividing by its initial value...

[ [ [ [ [ 1 A1 A2 A3 A4 ~ B1 B2 B3 B4 ~ C1 C2 C3 C4 ~ D1 D2 D3 D4 ~ E1 E2 E3 E4 ~ K1 K2 K3 K4 ] ] ] ] ]

Scale the top row by A1 and subtract it from the next row down and replacing...

[ [ [ [ [ 1 0 A2 A3 A4 ~ ~ B2 B3 B4 ~ ~ C2 C3 C4 ~ ~ D2 D3 D4 ~ ~ E2 E3 E4 ~ ~ K2 K3 K4 ] ] ] ] ]

Similarly, scale the top row by A2 and subtract it from the middle row. Then scale by A3 for row 3 and A4 for row4...

[ [ [ [ [ 1 0 0 0 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ] ] ] ] ]

Now, scale the second row down by its first nonzero coefficient...

[ [ [ [ [ 1 0 0 0 0 ~ 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ] ] ] ] ]

Next, force zeros in the second column the same as we did with the first, but using the second row for subtraction and substitution...

[ [ [ [ [ 1 0 0 0 0 ~ 1 0 0 0 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ] ] ] ] ]

Keep working your way through the array, this time scaling the third row down by its first nonzero term and then using scaled subtractions to zero out everything below in the same column. Eventually, you should end up with...

-- 76 . 2 --

[ [ [ [ [

1 0 0 0 0

~ 1 0 0 0

~ ~ 1 0 0

~ ~ ~ 1 0

~ ~ ~ ~ 1

~ ~ ~ ~ ~

] ] ] ] ]

This completes the Gauss part of the process. The lower right squiggle will be z by inspection! Relabel the above array...

[ [ [ [ [ 1 0 0 0 0 c01 c02 c03 c04 j05 ] 1 c12 c13 c14 j15 ] 0 1 c23 c24 j25 ] 0 0 1 c34 j35 ] 0 0 0 1 z ]

where cxx is the row and column coefficient for the left side equation terms, and jxx is the similar row and column coefficient for the right side equation term. The traditional way to solve this was by back substitution. You can start off with y = j35 - z*c34 and so on. And then work your way up a row at a time, making more complex calculations until you have v through z all solved. The Jordan approach starts off the same way, but it works one column at a time, greatly simplifying computer programming. Especially when more than one n x n equation set size is to be accommodated. The new rule is that any constant can

be subtracted from one term in the left side of the equation as long as that same constant get subtracted from the right side of the equation.

Subtract z*c34 from row 4...

[ [ [ [ [ 1 0 0 0 0 c01 c02 c03 c04 j05 ] 1 c12 c13 c14 j15 ] 0 1 c23 c24 j25 ] 0 0 1 0 y ] 0 0 0 1 z ]

So far, this is the same as the usual back substitution. We now can observe y by inspection The difference with Jordan is to continue by working columns instead of rows. Modify the rows by subtracting z*c24, z*c14, and z*c04 to get...

[ [ [ [ [ 1 0 0 0 0 c01 c02 c03 1 c12 c13 0 1 c23 0 0 1 0 0 0 0 0 0 0 1 ~ ] ~ ] ~ ] y ] z ]

-- 76 . 3 --

Next, modify column three by subtracting y*c23, y*c13, and y*c03. And then column two by subtracting x*c12 and x*c02. And finally column one by subtracting w*c01 to get...

[ [ [ [ [ 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 v] w] x] y] z]

Your values v through z are now instantly readable by inspection! Once again, the Jordan method takes just as many calculations as does a back substitution, but it greatly simplifies computation. In that loops do not have any multiple calculations or complicated cross-coefficients in them. This is especially handy when it comes to making the code n independent.

A Code Example

Here's a JavaScript program that solves n x n linear equations. It is amazingly compact, offers 64 bit arithmetic, and works for most any sane value of n. But it does not trap any div0's or handle wild coefficients. Per this main proc...

function solveGaussJordan() { gjNsize = eqns.length ; for (var iii = 0; iii