public class Matrix {
	public Fraction[][] M;
	public int rows;
	public int cols;
	
	public Matrix (int rows, int cols) {
		M = new Fraction[rows][cols];
		this.rows = rows;
		this.cols = cols;
	}
	
	public Matrix(Fraction[][] M) {
		rows = M.length;
		cols = M[0].length;
		
		this.M = new Fraction[rows][cols];
		
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				this.M[row][col] = M[row][col];
			}
		}		
	}
	
	public Matrix(String data, String delimeter) {
		String[] rowStrings = data.split("\n");
		String[][] fieldStrings = new String[rowStrings.length][];
		
		for (int i = 0; i < rowStrings.length; i++) {
			fieldStrings[i] = rowStrings[i].split(delimeter);
		}
		
		this.rows = fieldStrings.length;
		this.cols = fieldStrings[0].length;
		
		M = new Fraction[rows][cols];
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				M[i][j] = new Fraction(fieldStrings[i][j]);
			}
		}
	}
	
	public Matrix add(Matrix A) {
		Matrix sum = new Matrix(new Fraction[A.M.length][A.M[0].length]);
		for (int row = 0; row < M.length; row++) {
			for (int col = 0; col < M[0].length; col++) {
				sum.M[row][col] = this.M[row][col].add(A.M[row][col]); 
			}
		}
		return sum;
	}
	
	public Matrix multiply(Fraction a) {
		Matrix product = new Matrix(new Fraction[this.M.length][this.M[0].length]);
		// Compute the product
		for (int row = 0; row < M.length; row++) {
			for (int col = 0; col < M[0].length; col++) {
				product.M[row][col] = M[row][col].multiply(a); 
			}
		}
		return product;
	}
	
	public static Fraction dot(Fraction[] A, Fraction[] B) {
		Fraction dot = new Fraction(0,1);
		for (int col = 0; col < A.length; col++) {
			dot = dot.add(A[col].multiply(B[col]));
		}
		return dot;
	}
	
	public static Fraction[] colToArray(Matrix A, int col) {
		Fraction[] row = new Fraction[A.M.length];
		for (int i = 0; i < A.M.length; i++) {
			row[i] = A.M[i][col];
		}
		return row;
	}
	
	public static Fraction[] removeCol(Fraction[] a, int col) {
		Fraction[] b = new Fraction[a.length-1];
		int j = 0;
		for (int i = 0; i < a.length; i++) {
			if (i != col) b[j++] = a[i];
		}
		return b;
	}
	
	public static Fraction[][] removeRow(Fraction[][] a, int row) {
		Fraction[][] b = new Fraction[a.length-1][a[0].length];
		int j = 0;
		for (int i = 0; i < a.length; i++) {
			if (i != row) b[j++] = a[i];
		}
		return b;
	}
		
	public Matrix multiplyM(Matrix A) {
		Matrix product = new Matrix(new Fraction[M.length][A.M[0].length]);
		for (int row = 0; row < M.length; row++) {
			for (int col = 0; col < A.M[0].length; col++) {
				product.M[row][col] = dot(this.M[row], colToArray(A, col)); 
			}
		}
		return product;
	}
	
	public Matrix transpose() {
		Matrix transpose = new Matrix(new Fraction[M[0].length][M.length]);
		for (int row = 0; row < M[0].length; row++) {
			for (int col = 0; col < M.length; col++) {
				transpose.M[row][col] = M[col][row];
			}
		}
		return transpose;
	}
	
	public Matrix minorMatrix(int row, int col) {
		Fraction[][] a = removeRow(M, row);
			
		for (int i = 0; i < M.length - 1; i++) {
			a[i] = removeCol(a[i], col);
		}

		return new Matrix(a);
	}
	
	public Matrix matrixOfMinors() {
		Matrix matrixOfMinors = new Matrix(new Fraction[M.length][M[0].length]);	
		for (int row = 0; row < M.length; row++) {
			for (int col = 0; col < M[0].length; col++) {
				matrixOfMinors.M[row][col] = minorMatrix(row, col).det();
			}
		}
		return matrixOfMinors;
	}
	
	public Fraction det() {		
		if (M.length == 1) return M[0][0];

		Fraction det = new Fraction(0,1);
		for (int col = 0; col < M[0].length; col++) {
			//det += Math.pow(-1, col) * M[0][col] * minorMatrix(0, col).det();
			det = det.add(new Fraction((int)Math.pow(-1, col),1).multiply(M[0][col]).multiply(minorMatrix(0, col).det()));
		}
		return det;
	}
	
	public Matrix cofactorMatrix() {
		boolean flipSign = M[0].length % 2 == 0;
		Matrix matrixOfMinors = matrixOfMinors();
		Matrix cofactorMatrix = new Matrix(new Fraction[matrixOfMinors.M.length][matrixOfMinors.M[0].length]);
		Fraction sign = new Fraction(1,1);
		
		for (int row = 0; row < M.length; row++) {
			for (int col = 0; col < M[0].length; col++) {
				cofactorMatrix.M[row][col] = sign.multiply(matrixOfMinors.M[row][col]);
				sign = sign.multiply(new Fraction(-1,1));
			}
			if (flipSign) sign = sign.multiply(new Fraction(-1,1));
		}
		return cofactorMatrix;
	}
	
	public Matrix inverse() {
		Matrix adjugate = cofactorMatrix().transpose();
		Fraction det = det();
		return adjugate.multiply(new Fraction(det.d, det.n));
	}
	
	public String toString() {
		String s = "";
		for (int row = 0; row < M.length; row++) {
			for (int col = 0; col < M[0].length; col++) {
				s += M[row][col] + " ";
			}
			s+="\n";
		}	
		return s;
	}
}