/////////////////////////////////////////////////////////////////////////////////////////////
//
//   BasisRA.java
//   Determines bases for the image and kernal of a matrix
//
//   Save this file as BasisRA.java on any system with the javac compiler, available
//   from Sun Microsystems: http://java.sun.com/javase/downloads/index.jsp
//   If you're on a unix system also save the file "Makefile" in the same directory, then
//        Compile by typing "make" or "gmake" at the command line (leave out the quotes).
//        Run the executable by doing "BasisRA infile outfile", where "infile" is
//        a properly formated (described below) input file.
//   If you're on any other system, then
//        Compile by typing "javac BasisRA.java" at the command line (leave out quotes).
//        Run the executable by doing "java BasisRA infile outfile, where "infile" is
//        a properly formated (described below) input file.
//
//   Note: if "outfile" already exists in your working directory, then the above commands will
//         overwrite it.
//
//   Input file format.
//   The first line of an input file consists of two integers n and m, separated by a space,
//   giving the number of rows and columns, respectively.  The next n lines of the input file
//   specify the n rows of the matrix.  Each line is a space separated list of m rational numbers.
//   A rational number is specified by either a single integer, or a pair of integers separated
//   by a fraction bar. Note that the number of spaces separating the numbers in each row is
//   irrelevant.
//
//   Example 1  (Save the following lines as a text file called in1.)
//   3 5
//    2  0  4  2  9
//    3  4  0  0 -7
//    0  1  0  5  0
//
//   Example 2  (Save as text file in2.)
//   4 7
//    3    4/3  7/9  0    0    1    8/5
//   -6/7  1/2  3/4  5/6  7/8  0    0
//    9/8  7/6  5/4  3/2  2    2/3  4/5
//    6/7  8   -9    2/5  3    4/7 -5/5
//
//   Output file format.
//   The output will consist of three matrices.  The input matrix (nxm) will be reprinted,
//   followed by a matrix with n rows and r columns, where r is the rank of the input matrix.
//   This second matrix will consist of a subset of the columns of the input matrix which
//   form a basis for it's image.  The third matrix will have m rows and m-r columns, which
//   form a basis for the kernal of the input matrix.  The format of the matrix entries can
//   be adjusted by changing the vaules of the constant COLUMN_WIDTH below (line 60 of this
//   file).  COLUMN_WIDTH specifies the minimum number of characters to be printed in each
//   column (default 10).  If the number printed exceeds this width, the field will expand
//   to accomodate the extra characters.  There is a further space included after each column.
//   After changing this constant, you must recompile the program.
//
/////////////////////////////////////////////////////////////////////////////////////////////

import java.io.*;
import java.util.StringTokenizer;

class BasisRA{

   static final int COLUMN_WIDTH = 10;

   // swap()
   // swap row i with row k
   // pre: A[i][q]==A[k][q]==0 for 1<=q<j
   static void swap(Rational[][] A, int i, int k, int j){
      int m = A[0].length - 1;
      Rational temp;
      for(int q=j; q<=m; q++){
         temp = A[i][q];
         A[i][q] = A[k][q];
         A[k][q] = temp;
      }
   }

   // divide()
   // divide row i by A[i][j]
   // pre: A[i][j]!=0, A[i][q]==0 for 1<=q<j
   // post: A[i][j]==1;
   static void divide(Rational[][] A, int i, int j){
      int m = A[0].length - 1;
      for(int q=m; q>=j; q--) A[i][q].divEq(A[i][j]);
   }

   // eliminate()
   // subtract an appropriate multiple of row i from every other row
   // pre: A[i][j]==1, A[i][q]==0 for 1<=q<j
   // post: A[p][j]==0 for p!=i
   static void eliminate(Rational[][] A, int i, int j){
      int n = A.length - 1;
      int m = A[0].length - 1;
      for(int p=1; p<=n; p++){
         if( p!=i && !A[p][j].isZero() ){
            for(int q=m; q>=j; q--) A[p][q].subEq(A[p][j].mult(A[i][q]));
         }
      }
   }

   // printMatrix()
   // print the present state of Matrix A to file out
   static void printMatrix(PrintWriter out, Rational[][] A){
      int n = A.length - 1;
      int m = A[0].length - 1;
      StringBuffer format = new StringBuffer(" %-");
      format.append(COLUMN_WIDTH).append("s ");
      for(int i=1; i<=n; i++){
         for(int j=1; j<=m; j++) out.printf(format.toString(), A[i][j]);
         out.println();
      }
      out.println();
      out.println();
   }

   // main()
   // read input file, initialize matrix, perform Gauss-Jordan Elimination,
   // and write resulting matrices to output file
   public static void main(String[] args) throws IOException {
      int n, m, r, p, i, j, k, q, s;
      String line;
      StringTokenizer st;

      // check command line arguments, open input and output files
      if( args.length!=2 ){
         System.out.println("Usage: BasisRA infile outfile");
         System.exit(1);
      }
      BufferedReader in = new BufferedReader(new FileReader(args[0]));
      PrintWriter out = new PrintWriter(new FileWriter(args[1]));

      // read first line of input file
      line = in.readLine();
      st = new StringTokenizer(line);
      n = Integer.parseInt(st.nextToken());
      m = Integer.parseInt(st.nextToken());

      // declare A and B to be of size (n+1)x(m+1) and do not use index 0
      Rational[][] A = new Rational[n+1][m+1];
      Rational[][] B = new Rational[n+1][m+1];
      int[] b = new int[m+1]; // for marking columns of B

      // read next n lines of input file and initialize arrays A and B
      for(i=1; i<=n; i++){
         line = in.readLine();
         st = new StringTokenizer(line);
         for(j=1; j<=m; j++){
            A[i][j] = Rational.valueOf(st.nextToken());
            B[i][j] = A[i][j].copy();
         }
      }

      // close input file
      in.close();

      // perform Gauss-Jordan Elimination algorithm on matrix B, mark columns which
      // contain a leading 1, determine the rank and nullity, save matrix A for later use
      i = 1; j = 1;
      while( i<=n && j<=m ){
         b[j] = 0;  // mark col j as not containing a leading 1
         k = i; while( k<=n && B[k][j].isZero() ) k++;
         if( k<=n ){
            if( k!=i ) swap(B, i, k, j);
            if( B[i][j].compareTo(1) != 0 ) divide(B, i, j);
            eliminate(B, i, j);
            b[j] = 1; // mark col j as containing a leading 1
            i++;
         }
         j++;
      }
      r = i-1;  // rank(A)
      p = m-r;  // nullity(A)

      // determine an mxp matrix C whose columns form a basis of ker(A)
      Rational[][] C = new Rational[m+1][p+1];
      j = 1; k = 1;
      for(i=1; i<=m; i++){
         if( b[i]==1 ){
            for(q=1; q<j; q++) C[i][q] = Rational.valueOf(0);
            s = i;
            for(q=j; q<=p; q++){
               s++;
               while(b[s]==1) s++;
               C[i][q] = B[k][s].copy();
               C[i][q].negate();
            }
            k++;
         }else{
            for(q=1; q<j; q++) C[i][q] = Rational.valueOf(0);
            C[i][j] = Rational.valueOf(1);
            for(q=j+1; q<=p; q++) C[i][q] = Rational.valueOf(0);
            j++;
         }
      }

      // determine a nxr matrix D whose columns form a basis of im(A)
      Rational[][] D = new Rational[n+1][r+1];
      k = 1;
      for(j=1; j<=m; j++){
         if( b[j]==1 ){
            for(i=1; i<=n; i++) D[i][k] = A[i][j].copy();
            k++;
         }
      }

      // print A, C and D
      out.println("Input matrix A:");
      printMatrix(out, A);
      out.println("Basis for im(A):");
      printMatrix(out, D);
      out.println("Basis for ker(A):");
      printMatrix(out, C);


      // close output file
      out.close();
   }
}