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.

Although quite general, we shall describe the method by considering the below mentioned system of equations for the sake of clarity & simplicity.

Let the system of equations be

axⁿ+bx^(n-1)+………………….+m(mod p)= z1

axⁿ+bx^(n-1)+………………….+m(mod p) = z2

axⁿ+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 xⁿ from the second equation, we multiply the first equation by –a/a & then add it to the second equation. Similarly, to eliminate xⁿ 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

    a b m(modp) zm

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 xⁿ,x^n-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.