import java.io.*;
import java.text.*;
import java.util.Locale;

class NA28
{
  public static void pivot(double a[][],int o[],double s[],int k)
  {// GaussLU  pivoting process
    int n=a.length;
    int dummy1=0;
    double buyuk;
    double dummy=0;
    //pivotlama
	int p=k;
	buyuk=Math.abs(a[o[k]][k]);
	for(int ii=k+1;ii<n;ii++)
	{  dummy=Math.abs(a[o[ii]][k]/s[o[ii]]);
	   if(dummy > buyuk) {buyuk=dummy;p=ii;}
	}
	dummy1=o[p];
	o[p]=o[k];
	o[k]=dummy1;	   
  }
  
  public static int[] pivot_index(int n)
  {   // indexed the pivoted matrix 
	  int o[]=new int[n];
	  for(int i=0;i<n;i++) {o[i]=i;}
	  return o;
  }	  
  
  public static double[][] gaussLU(double ai[][],int o[])
  { //Gauss LU with pivoting
  int n=ai.length;	    
  double a[][]=new double[n][n];
  double s[]=new double[n];
  double carpan=0;
  double sum=0;
  double absaij;

  //gauss elimination
  int i,j,k,p,ii,jj;
  for(i=0;i<n;i++)
  {for(j=0;j<n;j++){a[i][j]=ai[i][j];}}
  for(i=0;i<n;i++)
  { o[i]=i;s[i]=Math.abs(a[i][0]);
    for(j=1;j<n;j++)
      { absaij=Math.abs(a[i][j]);
        if(absaij>s[i]) {s[i]=absaij;}
      }
  }
  for(k=0;k<(n-1);k++)
  { pivot(a,o,s,k);
	//change pivort reference		
	//solve gauss elimination  
    for(i=k+1;i<n;i++)
    {  carpan=a[o[i]][k]/a[o[k]][k];
       a[o[i]][k]=carpan;
       for(j=k+1;j<n;j++)
       {   a[o[i]][j]-=carpan*a[o[k]][j]; }
	}
  }
  return a;
  }
  
  public static double[] back_substiution(double ai[][],double bi[])
  {   int n=ai.length;
	  return back_substiution(ai,bi,pivot_index(n));
  }
  
  public static double[][] back_substiution(double ai[][],double bi[][])
  {   int n=ai.length;
	  return back_substiution(ai,bi,pivot_index(n));
  }  
  
  public static double[] back_substiution(double ai[][],double bi[],int o[])
  { 
    int n=ai.length;
    double sum;
    double x[]=new double[n];
    double a[][]=new double[n][n];
    double b[]=new double[n];
    int i,j;
    for(i=0;i<n;i++)
      {for(j=0;j<n;j++){a[i][j]=ai[i][j];};b[i]=bi[i];}               
  for(i=1;i<n;i++)
      {sum=b[o[i]];for(j=0;j<i;j++){sum-=a[o[i]][j]*b[o[j]];};b[o[i]]=sum;}     
  x[n-1]=b[o[n-1]]/a[o[n-1]][n-1];
  for(i=(n-2);i>=0;i--)
      {sum=0;      
       for(j=i+1;j<n;j++)      
        {sum+=a[o[i]][j]*x[j];};
        x[i]=(b[o[i]]-sum)/a[o[i]][i];
      }      
  return x;              
  }  
  
  public static double[][] back_substiution(double ai[][],double bi[][],int o[])
  {
    int n=ai.length;
    int m=bi[0].length;
    double sum;
    double x[][]=new double[n][m];
    double a[][]=new double[n][n];
    double b[][]=new double[n][m];
    int i,j,k;
  for(i=0;i<n;i++)
      {for(j=0;j<n;j++){a[i][j]=ai[i][j];};for(k=0;k<m;k++) {b[i][k]=bi[i][k];}}                
  for(k=0;k<m;k++)
  {
  for(i=1;i<n;i++)
      {sum=b[o[i]][k];for(j=0;j<i;j++){sum-=a[o[i]][j]*b[o[j]][k];};b[o[i]][k]=sum;}     
  x[n-1][k]=b[o[n-1]][k]/a[o[n-1]][n-1];
  for(i=(n-2);i>=0;i--)
      {sum=0;      
       for(j=i+1;j<n;j++)      
        {sum+=a[o[i]][j]*x[j][k];};
        x[i][k]=(b[o[i]][k]-sum)/a[o[i]][i];
      }
  }    
  return x;          
  }
  
  public static double [] AXB(double a[][],double b[])
  {
  //solution of the system of equation  
  int n=a.length;	  
  int q[]=new int[n];
  double c[][]=gaussLU(a,q);
  double s[]=back_substiution(c,b,q);
  return s;
  }
  
  public static double [][] AXB(double a[][],double b[][])
  {//solution of the set of the system  of equations  
  int n=a.length;	  
  int q[]=new int[n];
  double c[][]=gaussLU(a,q);
  double s[][]=back_substiution(c,b,q);
  return s;
  }
  
  public static double[][] I(int n)
  {
  //Inverse matrix
  double b[][];
  b=new double[n][n];
  for(int i=0;i<n;i++)
    b[i][i]=1.0;
  return b;
  }
  
  public static double[][] inverse(double a[][])
  {
  //Inverse matrix	  
  int n=a.length;	  
  int q[]=new int[n];
  double c[][]=gaussLU(a,q);
  double s[][]=back_substiution(c,I(n),q);
  return s;
  }
  
  // Matrix output classes
  public static String toString(double[][] left)
  {
  //return a string representation of a matrix
  return toString(left,25,15);
  }
  public static String toString(double[][] left,int w,int d)
  {
  //return a string representation of a matrix
  int n,m;
  String b;
  b="";
  n=left.length;
  m=left[0].length;
  for(int i=0;i<n;i++)
  {
  for(int j=0;j<m;j++)
    {
    b=b+toString(left[i][j],w,d);
    }
    b=b+"\n";
  }
  return b;
  }
  
  public static String toString(double left, int w, int d)
  // converts a double to a string with given width and decimals.
  {	
	Locale us=new Locale("US");
	String s="%"+w+"."+d+"f";
	String s1=String.format(us,s,left);  
    return s1;
  }
  
  public static void main(String args[]) throws IOException
  {
  double a[][]={{8,2,3},{1,-9,2},{2,3,6}};
  System.out.println("Matrix a : \n"+toString(a)); 
  System.out.println("Inverse Matrix of a : \n"+toString(inverse(a)));
  }
}