Upper Triangular Matrix by Row Operation

It explains how to decompose an augmented matrix into upper triangular matrix by row operation and it is implemented in Java programming.

A system of linear equation is represented in matrix format by a matrix called A and two column vectors called X and b respectively.

AX =b

The X is an unknown vector and is to be found as solution for a system of linear equations.

The Gaussian elimination is one of the methods for finding the unknown vector of a linear system of equations.

The Gaussian elimination has two main steps

1. Augmented matrix into Upper Triangular
2. Back substitution

Here, it contains explanation about how to decompose an augmented matrix into upper triangular matrix.

The augmented matrix consist of coefficient matrix A and a column vector b i.e. Alb and it is decomposed into upper triangular matrix by elementary row operation.

A matrix has rows and columns arrangements of elements and if all elements below the main diagonal elements are zeros, it is called upper triangular matrix.

Upper Triangular matrix algorithm steps

Given matrix A, b and
A is 3x3 and b is 3x1 matrix

1. make Augmented Matrix by A and b
• mat = [ A|b ]
2. swap rows for maximum pivotal value along r^th column
3. find ratio = mat[r+1][r] / mat[r][r]
4. subtract ratio times r^th row and r+1^th row
• R _r+1 <- ratio x R_r - R _r+1

Upper Triangular Matrix Example

Given System of Linear Equation \[\begin{array}{c} 4.0x+5.0y-2.0z=-14 \\ 7.0x-1.0y+2.0z=42 \\ 3.0x+1y+4.0z=28 \end{array} \] Augmented matrix A|b \[ \left[\begin{array}{rrr|r} 4.0 & 5.0 & -2.0 & -14.0 \\ 7.0 & -1.0 & 2.0 & 42.0 \\ 3.0 & 1.0 & 4.0 & 28.0 \\ \end{array} \right] \]

swap 0^th row and 1^st row
R₀ <-> R₁

\[ \left[\begin{array}{rrr|r} 7.0 & -1.0 & 2.0 & 42.0 \\ 4.0 & 5.0 & -2.0 & -14.0 \\ 3.0 & 1.0 & 4.0 & 28.0 \\ \end{array} \right] \]

To make R₁₀ element to zero, divide R₁₀ by R₀₁
ratio = 4.0/7.0 = 0.571
ratio = 0.571 multiplied by (-1) minus
Add -0.571 times 0^th row to 1^st row
R₁ <- 0.571*R₀+R₁

\[ \left[\begin{array}{rrr|r} 7.0 & -1.0 & 2.0 & 42.0 \\ 0.0 & 5.5714 & -3.1428 & -38.0 \\ 3.0 & 1.0 & 4.0 & 28.0 \\ \end{array} \right] \]

To make R₂₀ element to zero, divide R₂₀ by R₀₁
ratio = 3.0/7.0 = 0.4285
ratio = 0.4285 multiplied by (-1) minus
Add -0.4285 times 0^th row to 2^nd row
R₂ <- 0.4285*R₀+R₂

\[ \left[\begin{array}{rrr|r} 7.0 & -1.0 & 2.0 & 42.0 \\ 0.0 & 5.57143 & -3.1428 & -38.0 \\ 0.0 & 1.42857 & 3.1428 & 10.0 \\ \end{array} \right] \]

To make R₂₁ element to zero, divide R₂₁ by R₁₁
ratio = 1.42857/5.57143 = 0.256
ratio = 0.256 multiplied by (-1) minus
Add -0.256 times 1^st row to 2^nd row
R₂ <- -0.256*R₁+R₂ \[ \left[\begin{array}{rrr|r} 7.0 & -1.0 & 2.0 & 42.0 \\ 0.0 & 5.5714 & -3.14285 & -38.0 \\ 0.0 & 0.0 & 3.94871 & 19.7435 \\ \end{array} \right] \] Upper Triangular matrix \[ \left[\begin{array}{rrr|r} 7.0 & -1.0 & 2.0 & 42.0 \\ 0.0 & 5.5714 & -3.14285 & -38.0 \\ 0.0 & 0.0 & 3.94871 & 19.7435 \\ \end{array} \right] \]

Upper Triangular matrix pseudo-code steps

       For r =0  to mat.Nrow-1

            mr =maxpivot(r);
            RowOperation-swap(r,mr);

            For r2 =r+1  to mat.Nrow-1
                ratio = mat[r2][r] / mat[r][r]
                RowOperation-subtract(mat,r2,r,-ratio)
            End

      End

      note  - maxpivot function finds mrth row has maximum value along rth column 
   

Upper Triangular matrix in Java

The Java class,Triangular converts Augmented matrix into upper triangular matrix by elementary row operation.

 
public class Triangular {
  
    Matrix mat; 
 public Triangular(double A[][],double b[]) {
  
  int row=A.length;
  int col=A[0].length;
  
  mat = new Matrix(row,col+1);
  for(int r=0;r<row;r++) {
   for(int c=0;c<col;c++) 
        mat.setElement(r, c, A[r][c]);    
  }
  
  for(int r=0;r<row;r++) 
   mat.setElement(r, col, b[r]);  
 }
 
 public Matrix upper() {
   return Triangular.upper(mat);
 }
 
 public String toString() {
  return mat.toString();
 }
 
 public static int maxpivot(Matrix mat,int c) {
  
  int mr=0; double mx=0;
  for(int r=0;r<mat.getNrow();r++) 
  { 
   if (   mat.getElement(r, c) > mx ) {
      mx = mat.getElement(r, c);
      mr = r;
   }
  }
  return mr;
 }
 
 public static Matrix upper(Matrix mat) {
              
     for(int r=0;r<mat.getNrow();r++) 
     {    
        int mr = Triangular.maxpivot(mat,r);
        RowOperation.swap(mat, r, mr);
        for(int r2=r+1;r2<mat.getNrow();r2++) 
         {
          double m= mat.getElement(r2, r) / mat.getElement(r, r);
           RowOperation.subtract(mat, r2, r, m);
         }
       }  
    return mat;
 }

 public static void main(String[] args) {

  double A[][]= { {4,5,-2},{7,-1,2},{3,1,4}};
  double b[]= {-14,42,28};
  
  Triangular tri =new Triangular(A,b);
  System.out.println("Augmented matrix");
  System.out.println(tri.toString());
  
  Matrix U =tri.upper();
  System.out.println("Upper Triangular matrix");
  System.out.println(U.toString());
      
 }

}
 

Java programming Upper Triangular matrix output

Augmented matrix
4.0  5.0  -2.0  -14.0  
7.0  -1.0  2.0  42.0  
3.0  1.0  4.0  28.0  

Upper Triangular matrix
7.0  -1.0  2.0  42.0  
0.0  5.571428571428571  -3.142857142857143  -38.0  
0.0  0.0  3.948717948717949  19.743589743589745