" I would like to show my Acknowledgement and special Thanks to the Original Author Of Many of the Programs in this Blog : Sir A.K. Seal who has shown great teaching skills to make Programming Practical and Simple. "Objective :
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix. The method is named after Carl Friedrich Gauss, but it was not invented by him.
Elementary row operations are used to reduce a matrix to what is called triangular form (in numerical analysis) or row echelon form (in abstract algebra). Gauss–Jordan elimination, an extension of this algorithm, reduces the matrix further to diagonal form, which is also known as reduced row echelon form. Gaussian elimination alone is sufficient for many applications, and requires fewer calculations than the Gauss–Jordan version.
The process of Gaussian elimination has two parts. The first part (Forward Elimination) reduces a given system to either triangular or echelon form, or results in a degenerate equation, indicating the system has no unique solution but may have multiple solutions. This is accomplished through the use of elementary row operations. The second step uses back substitution to find the solution of the system above.
Stated equivalently for matrices, the first part reduces a matrix to row echelon form using elementary row operations while the second reduces it to reduced row echelon form, or row canonical form.
Another point of view, which turns out to be very useful to analyze the algorithm, is that Gaussian elimination computes a matrix decomposition. The three elementary row operations used in the Gaussian elimination (multiplying rows, switching rows, and adding multiples of rows to other rows) amount to multiplying the original matrix with invertible matrices from the left. The first part of the algorithm computes an LU decomposition, while the second part writes the original matrix as the product of a uniquely determined invertible matrix and a uniquely determined reduced row-echelon matrix.
BlueJ Program Screenshot :Example :
Suppose the goal is to find and describe the solution(s), if any, of the following system of linear equations:
The algorithm is as follows: eliminate x from all equations below 
, and then eliminate y from all equations below 
. This will put the system into triangular form. Then, using back-substitution, each unknown can be solved for.
, and then eliminate y from all equations below . This will put the system into triangular form. Then, using back-substitution, each unknown can be solved for.
In the example, x is eliminated from by adding 
to . x is then eliminated from 
by adding to . Formally:
by adding to . x is then eliminated from by adding to . Formally:
The result is:
Now y is eliminated from by adding 
to :
by adding to :
The result is:
This result is a system of linear equations in triangular form, and so the first part of the algorithm is complete.
The last part, back-substitution, consists of solving for the knowns in reverse order. It can thus be seen that
Then, 
can be substituted into , which can then be solved to obtain
can be substituted into , which can then be solved to obtain
Next, z and y can be substituted into , which can be solved to obtain
, which can be solved to obtain
The system is solved.
Some systems cannot be reduced to triangular form, yet still have at least one valid solution: for example, if y had not occurred in and after the first step above, the algorithm would have been unable to reduce the system to triangular form. However, it would still have reduced the system to echelon form. In this case, the system does not have a unique solution, as it contains at least one free variable. The solution set can then be expressed parametrically (that is, in terms of the free variables, so that if values for the free variables are chosen, a solution will be generated).
and after the first step above, the algorithm would have been unable to reduce the system to triangular form. However, it would still have reduced the system to echelon form. In this case, the system does not have a unique solution, as it contains at least one free variable. The solution set can then be expressed parametrically (that is, in terms of the free variables, so that if values for the free variables are chosen, a solution will be generated).
In practice, one does not usually deal with the systems in terms of equations but instead makes use of the augmented matrix (which is also suitable for computer manipulations). For example:
Therefore, the Gaussian Elimination algorithm applied to the augmented matrix begins with:
![\left[ \begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
-3 & -1 & 2 & -11 \\
-2 & 1 & 2 & -3
\end{array} \right]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uYrHBoz4rJvcRZvG6-8C7F4SWu2HMJOAelhQenySk5AF13ZUVgKVdZuLuOgBDdO610uZctjn6Yg6Z5bkwVyLu0DCpadBkICDzJJ1FtwjYqZ0hZxrsxRv8JbN0hyxQSGZc5CEFtcFFWjwO6JSz71HZTJzyDGQGJ2ba8wTI=s0-d)
which, at the end of the first part (Gaussian elimination, zeros only under the leading 1) of the algorithm, looks like this:
![\left[ \begin{array}{ccc|c}
1 & \frac{1}{3} & \frac{-2}{3} & \frac{11}{3} \\
0 & 1 & \frac{2}{5} & \frac{13}{5} \\
0 & 0 & 1 & -1
\end{array} \right]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vACuaToAH0deEoT8XrwtV3JKwx4Wj7PGKgjF-YPRqXIoe5BYa_aV6eatK1iV0LrydCkiSv3TdUPRo3oXA1ZMbfHDc_JuFJRrS21J2OBSUf6bSDvQYSHNo5p1Gh9huIgOpiAOWNSdb5gyd9GQuha8yxthm8dPoLZTBtYJg=s0-d)
That is, it is in row echelon form.
At the end of the algorithm, if the Gauss–Jordan elimination(zeros under and above the leading 1) is applied:
![\left[ \begin{array}{ccc|c}
1 & 0 & 0 & 2 \\
0 & 1 & 0 & 3 \\
0 & 0 & 1 & -1
\end{array} \right]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_skiiQDaDp4rdYbwUjYT85SsxoyEBEu15yAKTUnxYd77HEB4MsruGLc0UpkEgvvOq2Ng9v3SiB4nFKi-yUYbq1ISMep_JuYm6RLd8EyynmdcRKBUvyyl2pPLp7Vk8fknxxuzsX0uNgZVusJYADaiXVtsGu2du79O4g7Bzg=s0-d)
That is, it is in reduced row echelon form, or row canonical form.
Java Program Source Code :
/**
* The Program Takes Number of Eqautions and Then Creates An
* Square Matrix of Order x Order and Formulates a Top Triangle
* My Continuous Elimination and Then Solves the Set of Equations
* to Find the Values of the Order number of Variables.
* @author SHANTANU KHAN
* @mail shantanukhan1995@gmail.com
* @website 0code.blogspot.com
* Program Type : BlueJ Program - Java
*/
import java.util.*;
public class GaussMatrix
{
// INSTANCE VARIABLES
private double[][] m; // MATRIX OF CO-EFFICIENTS
private double[] constants; // VECTOR OF CONSTANT TERMS
private double[] solution; // SOLUTION SET
private int numEq; // NUMBER OF EQUATIONS
static Scanner sc=new Scanner(System.in);
public GaussMatrix(int equations) // CONSTRUCTOR
{
numEq=equations;
m=new double[numEq][numEq];
constants=new double[numEq];
solution=new double[numEq];
}
public void fillMatrix()
{
for(int i=0;i<numEq;i++){
System.out.println("Enter the co-efficients of unknowns and constant term for Equation "+(i+1)+" :");
for(int j=0;j<numEq;j++){
System.out.print("Enter Co-efficient "+(j+1)+" : ");
m[i][j]=sc.nextDouble();
}
System.out.print("Enter Constant Term : ");
constants[i]=sc.nextDouble();
}
}
public void printSolution()
{
System.out.println("\nSolution Set is : ");
for(int i=0;i<numEq;i++)
System.out.println((char)('A'+i)+" = "+solution[i]);
}
public void printMatrix() // FOR DEBUGGING PURPOSE
{
for(int i=0;i<numEq;i++){
for(int j=0;j<numEq;j++){
if(m[i][j]>=0)
System.out.print(" +"+m[i][j]+((char)('A'+j))+" ");
else if(m[i][j]<0)
System.out.print(" "+m[i][j]+((char)('A'+j))+" ");
}
System.out.println(" = "+constants[i]);
}
}
public void swapRows(int row1,int row2)
{
double temp;
for(int j=0;j<numEq;j++){ // SWAPPING CO-EFFICIENT ROWS
temp=m[row1][j];
m[row1][j]=m[row2][j];
m[row2][j]=temp;
}
temp=constants[row1]; // SWAPPING CONSTANTS VECTOR
constants[row1]=constants[row2];
constants[row2]=temp;
}
public void eliminate()
{
int i,j,k,l;
for(i=0;i<numEq;i++){ // i -> ROW ; MATRIX ORDER DECREASES DURING ELIMINATION
// FIND LARGEST CO-EFFICIENTSOF THE CURRENT COLUMN MOVING ROW-WISE
double largest=Math.abs(m[i][i]);
int index=i;
for(j=i+1;j<numEq;j++){
if(Math.abs(m[j][i])>largest){
largest=m[j][i];
index=j;
}
}
swapRows(i,index); // SWAPPING i-th ROW to index-th ROW
for(k=i+1;k<numEq;k++){
double factor=m[k][i]/m[i][i];
// PROCESSING COLUMN WISE
for(l=i;l<numEq;l++){
m[k][l]-=factor*m[i][l];
}
constants[k]-=factor*constants[i]; // PROCESSING CONSTANTS
}
}
}
public void solve()
{
for(int i=numEq-1;i>=0;i--){
solution[i]=constants[i]; // COPY
for(int j=numEq-1;j>i;j--){
solution[i]-=m[i][j]*solution[j];
}
solution[i]/=m[i][i];
}
}
public static void main(String args[])
{
System.out.print("Enter the Number of Terms : ");
GaussMatrix obj=new GaussMatrix(sc.nextInt());
obj.fillMatrix();
System.out.println("\fYou Have Entered The Following Equations :");
obj.printMatrix();
obj.eliminate();
obj.solve();
obj.printSolution();
