How can we apply the Gauss Elimination method to solve m question?
Recently a user to the Indian Math Online web site submitted a question for one of our math experts. The user who we will refer to only by first name - Amresh - submitted this question and picked "Grade 1" as the grade. We do not believe this is a question from a 1st Grader. This is a question for higher grades, perhaps even taught in early years of Engineering programs.
Here we go - the question first;
"How can we apply the Gauss Elemination method to solve m equation? For example z1 = ax^n + bx^(n-1) + ... + m (mod p) z2 = ax^n + bx^(n-1) + ... + m (mod p) ..................................... ..................................... ..................................... zm = ax^n + bx^(n-1) + ... + m (mod p) I want the mod p vale of a,b,c... "
Our answer follows - if after reading the answer, you have more questions or need further clarifications, please click here. A pdf version of the answer can be downloaded here.
Gaussian elimination method:
This is an elementary elimination method & it reduces the system of equations to an equivalent upper triangular system which can then be solved by back substitution.
Let the system of equations be
axn+bx(n-1)+………………….+m(mod p)= z1
axn+bx(n-1)+………………….+m(mod p) = z2
axn+bx(n-1)+………………….+m(mod p)= zm
We first form the augmented matrix
![]()
![]()
![]()
a b m(modp) z1
a b m(modp) z2
a b m(modp) zm
To eliminate xn from the second equation, we multiply the first equation by –a/a & then add it to the second equation. Similarly, to eliminate xn from the third equation, we multiply the first equation by –a/a & then add it to the third equation. This procedure can be shown thus:
![]()
![]()
![]()
a b m(modp) z1
-a/a a b m(modp) z2
-a/a a b m(modp) z3
![]()
where –a/a & -a/a are called multipliers for the first stage of elimination. In this stage, it is assumed that the first element in the first equation a≠ 0. The first equation is called the pivotal equation & the first element a is called first pivot. At the end of the first stage, the augmented matrix becomes:
![]()
![]()
![]()
a b m(modp) z1
0 b’ m(modp)’ z2’
0 b’ m(modp)’ z3’
-a/a 0 b’ m(modp) ‘ zm’
where b’,(modp)’……….. are all
changed elements. The first b’ of the
second equation is the new pivot &
the multiplier is –b’/b’.
After completing all stages, we should have the upper triangular system:
![]()
![]()
![]()
a b m(modp) z1
0 b’ m(modp)’ z2’
0 0 m(modp)’ z3’
0 0 0 zm’
![]()
from which the values of xn,xn-1 can be obtained by back substitution.
Those values will be substituted in the original system to get a system of equations
which can be solved to get the values of a,b, c etc
It is clear that this method will fail if one of the pivots vanishes. In such a case , the method can be modified by rearranging the rows so that the pivot is non-zero. This procedure is called partial pivoting & can be implemented on a computer.
If this is not possible, then the matrix is singular & the equations have no solution.
In particular, the number of non zero diagonal elements in the final augmented matrix will represent the rank of the original matrix.
Comments