Binary matrix (Java)

From LiteratePrograms

Binary matrix is a Java class that deals with binary matrix operation. It implements basic matrix operations such as addition, subtraction, and multiplication. This package may be used later in many applications such as Hamming (7, 4) code.

For convenience, we assume that A denotes the given binary matrix. B denotes the operand matrix .

To do:

• getDeterminant: returns the determinant.
• inverse: matrix inversion
• random: generates a matrix with random elements

Contents 1 Data 2 Constructors 3 Getter 4 Setter 5 Equals 6 Negate 7 Add 8 Subtract 9 Multiply 10 Inverse 11 Transpose 12 String representation 13 Test 14 The Whole Class

Data

Binary matrix is stored as a two-dimensional array of boolean values, because binary matrix is composed of either 0 or 1. false represents 0, and true represents 1.

• row is the number of rows.
• col is the number of columns.
• A is a two-dimensional array of boolean values.

<<Data>>=
  private boolean A[][];
  private int row;
  private int col;

Constructors

• BMatrix(int m, int n) initializes an m-by-n zero binary matrix.
• BMatrix(int input[][]) initializes a binary matrix from a two-dimensional integer array.
• BMatrix(boolean input[][]) initializes a binary matrix from a two-dimensional boolean array.
• BMatrix(int n) initializes an n-by-n identity matrix.

<<Constructor>>=
  public BMatrix(int m, int n) {
    this.row = m;
    this.col = n;
    this.A = new boolean[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        A[i][j] = false;
      }
    }
  }
  public BMatrix(int input[][]) {
    this.row = input.length;
    this.col = input[0].length;
    this.A = new boolean[this.row][this.col];
    for (int i = 0; i < this.row; i++) {
      for (int j = 0; j < this.col; j++) {
        if (input[i][j] == 0) {
          A[i][j] = false;
        } else {
          A[i][j] = true;
        }
      }
    }
  }
  public BMatrix(boolean input[][]) {
    this.row = input.length;
    this.col = input[0].length;
    this.A = new boolean[this.row][this.col];
    for (int i = 0; i < this.row; i++) {
      for (int j = 0; j < this.col; j++) {
        A[i][j] = input[i][j];
      }
    }
  }
  public BMatrix(int n) {
    this(n, n);
    for (int i = 0; i < n; i++) {
      this.set(i, i, true);
    }
  }

Getter

• The getRowDim method returns the row dimension.
• The getColDim method returns the column dimension.
• The getArray method returns the internal two-dimensional array.
• The get(i, j) method returns a single element A[i, j].
• The getMatrix(i0, j0, i1, j1) method returns a submatrix A[i0:i1, j0:j1]. If the index is out of bound, we raise an ArrayIndexOutOfBoundsException.

<<Getter>>=
  public int getRowDim() {
    return this.row;
  }
  public int getColDim() {
    return this.col;
  }
  public boolean[][] getArray() {
    return this.A;
  }
  public boolean get(int i, int j) {
    return A[i][j];
  }
  public BMatrix getMatrix(int i0, int j0, int i1, int j1){
    int row = i1 - i0 + 1;
    int col = j1 - j0 + 1;
    BMatrix result = new BMatrix(row, col);
    try {
      for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
          result.set(i, j, this.get(i + i0, j + j0));
        }
      }
    } catch(ArrayIndexOutOfBoundsException e) {
      throw new ArrayIndexOutOfBoundsException("Submatrix indices.");
    }
    return result;
  }

Setter

• The set(i, j, value) method sets the value of A[i, j] to value.

<<Setter>>=
  public void set(int i, int j, boolean value) {
    A[i][j] = value;
  }
  public void setMatrix(int i0, int j0, int i1, int j1, BMatrix X){
    try {
      for (int i = i0; i <= i1; i++) {
        for (int j = j0; j <= j1; j++) {
          this.set(i, j, this.get(i - i0, j - j0));
        }
      }
    } catch(ArrayIndexOutOfBoundsException e) {
      throw new ArrayIndexOutOfBoundsException("Submatrix indices.");
    }
  }

Equals

The equals method checks whether A = B.

<<Equals>>=
  public boolean equals(BMatrix B) {
    if ((this.row != B.getRowDim()) ||(this.col != B.getColDim())) {
      return false;
    } else {
      for (int i = 0; i < this.row; i++) {
        for (int j = 0; j < this.col; j++) {
          if (this.get(i, j) != B.get(i, j)) {
            return false;
          }
        }
      }
    }
    return true;
  }

Negate

The negate method toggles every element in A.

<<Negate>>=
  public void negate() {
    for (int i = 0; i < this.row; i++) {
      for (int j = 0; j < this.col; j++) {
        if (this.get(i, j)) {
          this.set(i, j, false);
        } else {
          this.set(i, j, true);
        }
      }
    }
  }

Add

The add method computes A + B. As the addition is defined on binary matrices, it can be simplified to bitwise operation.

• If A[i,j] is true. Then A[i,j] + B[i,j] is just inverting B[i,j].
• Otherwise, A[i,j] + B[i,j] is just same as B[i,j].

If the dimensions of A and B are different, we raise an IllegalArgumentException.

<<Add>>=
  public BMatrix add(BMatrix B) {
    int bCol = B.getColDim();
    int bRow = B.getRowDim();
    if (bCol == this.col && bRow == this.row) {
      BMatrix result = new BMatrix(B.getArray());
      for (int i = 0; i < this.row; i++) {
        for (int j = 0; j < this.col; j++) {
          // Invert the value when the operand is true.
	  if (B.get(i,j)) {
            result.set(i, j, !this.get(i,j));
          } else {
            result.set(i, j, this.get(i, j));
          }
        }
      }
      return result;
    } else {
      throw new IllegalArgumentException("Different dimensions.");
    }
  }

Subtract

The sub method computes A - B. Internally, it runs negate method to obtain -B.

<<Subtract>>=
  public BMatrix sub(BMatrix B) {
    B.negate();
    BMatrix Bminus = new BMatrix(B.getArray());
    BMatrix result = this.add(Bminus);
    return result;
  }

Multiply

The mul method computes A * B. If A is an m-by-n matrix and B is an n-by-p matrix, then their product is an m-by-p matrix. The product is given by

If the number of columns of A is different from the number of rows of B, we raise an IllegalArgumentException.

<<Multiply>>=
  public BMatrix mul(BMatrix B) {
    int bRow = B.getRowDim();
    int bCol = B.getColDim();
    if (bRow != this.col) {
      throw new IllegalArgumentException(this.row + "-by-" + this.col + ", " + bRow);
    } else {
      BMatrix result = new BMatrix(this.getRowDim(), bCol);
      for (int i = 0; i < this.getRowDim(); i++) {
        for (int j = 0; j < bCol; j++) {
          for (int k = 0; k < bRow; k++) {
            // Toggle the output only when two inputs are 1.
            if (this.get(i, k) && B.get(k, j)) {
              result.set(i, j, !result.get(i, j));
            }
          }
        }
      }
      return result;
    }
  }

Inverse

Calculating matrix inverses is difficult. An efficient method is to first calculate the LU decomposition and then use back-substitution to solve for the inverse. Thus we first require an implementation of an LU decomposition.

<<LU decomposition>>=
  private BMatrix[] pivot() {
    BMatrix output = new BMatrix(A);
    BMatrix permutation = new BMatrix(this.getRowDim());
    boolean[][] parityInitializer = {{false}};
    BMatrix parity = new BMatrix(parityInitializer);
    for (int j = 0; j < this.getColDim(); j++) {
      if (!this.get(j, j)) {
        for (int i = j; i < this.getRowDim(); i++) {
          if (this.get(i,j)) {
            output.swapRows(i,j);
            permutation.swapRows(i,j);
            parity.set(0, 0, !parity.get(0, 0));
	    break;
          }
        }    
      }
    }
    BMatrix[] result = new BMatrix[3];
    result[0] = output;
    result[1] = permutation;
    result[2] = parity;
    return result;
  }
  public BMatrix[] LUDecomposition() {
    if (this.getRowDim() != this.getColDim()) {
      throw new UnsupportedOperationException("Matrix is not square");
    }
    BMatrix lower = new BMatrix(this.getRowDim(), this.getColDim());
    BMatrix upper = new BMatrix(this.getRowDim());
    BMatrix[] input = pivot();
    // Initialise first column of lower, and first row of upper
    for (int i = 0; i < this.getRowDim(); i++) {
      lower.set(i, 0, input[0].get(i, 0));
      upper.set(0, i, input[0].get(0, i));
    }
    int n;
    boolean parity;
    for (int i = 0; i < this.getRowDim(); i ++) {
      // Determine column i of lower
      for (int j = i; j < this.getColDim(); j++) {
    	for (n = 0, parity = true; n < i; n++) {
    	  if (lower.get(j, n) && upper.get(n, i)) {
    	    parity = !parity;
    	  }
    	}
    	if (parity) {
    	  lower.set(j, i, input[0].get(j, i));
    	} else {
    	  lower.set(j, i, !input[0].get(j, i));
    	}
      }
      // Determine row i of upper
      for (int j = i + 1; j < this.getRowDim(); j++) {
    	for (n = 0, parity = true; n < i; n++) {
    	  if (lower.get(i, n) && upper.get(n, j)) {
    	    parity = !parity;
          }
    	}
    	if (parity) {
    	  lower.set(i, j, input[0].get(i, j));
    	} else {
    	  lower.set(i, j, !input[0].get(i, j));
    	}    			
      }
    }
    BMatrix[] result = new BMatrix[4];
    result[0] = lower;
    result[1] = upper;
    result[2] = input[1];
    result[3] = input[2];
    return result;
  }

The inverse method returns A^-1.

<<Inverse>>=
LU decomposition
  private BMatrix backSub(BMatrix[] luDecomp, BMatrix vector) {
    // Correct vector for permutation in LU decomp:
    BMatrix b = luDecomp[2].mul(vector);
    // Solve Ly = b by forward substitition
    BMatrix y = new BMatrix(vector.getRowDim(), vector.getColDim());
    y.set(0, 0, b.get(0, 0));
    boolean parity;
    int j;
    for (int i = 1; i < vector.getRowDim(); i++) {
      for (parity = true, j = 0; j < i; j++) {
        if (luDecomp[0].get(i,j) && y.get(j,0)) {
      	  parity = !parity;
        }    
      } 
      if (parity) {
        y.set(i, 0, b.get(i,0));
      } else {
        y.set(i, 0, !b.get(i,0));
      }
    }
    // Solve Ux = y by back substitution
    BMatrix x = new BMatrix(vector.getRowDim(), vector.getColDim());
    x.set(vector.getRowDim(), 0, x.get(0, 0));
    for (int i = vector.getRowDim(); i >= 0; i--) {
      for (parity = true, j = i + 1; j < vector.getRowDim(); j++) {
      	if (luDecomp[1].get(i,j) && x.get(j,0)) {
          parity = !parity;
        }
      }
      if (parity) {
        x.set(i, 0, y.get(i,0));
      } else {
        x.set(i, 0, !y.get(i,0));
      }
    }
    return x;
  }
  public BMatrix inverse() {
    if (this.getRowDim() != this.getColDim()) {
      throw new UnsupportedOperationException("Matrix is not square");
    }    	
    BMatrix[] luDecomp = this.LUDecomposition();
    BMatrix result = new BMatrix(this.getRowDim(), this.getColDim());
    BMatrix vector = new BMatrix(this.getRowDim(), 1);
    for (int i = 0; i < this.getColDim(); i++) {
      vector.set(i, 0, true);
      BMatrix column = backSub(luDecomp, vector);
      result.setMatrix(0, this.getRowDim(), i, i, column);
      // For next pass
      vector.set(i, 0, false);
    }
    return result; 
  }

Transpose

The transpose method returns the transpose matrix A^T.

<<Transpose>>=
  public BMatrix transpose() {
    BMatrix X = new BMatrix(this.col, this.row);
    for (int i = 0; i < this.col; i++) {
      for (int j = 0; j < this.row; j++) {
        X.A[i][j] = this.A[j][i];
      }
    }
    return X;
  }

String representation

We override the toString method for string representation of a binary matrix.

<<String_representation>>=
  public String toString() {
    String result = new String();
      for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
          if (this.get(i, j)) {
            result += "1 ";
          } else {
            result += "0 ";
          }
        }
       result += "\n";
      }
    return result;
  }

Test

This chunk is used to test the whole class.

<<Test>>=
  public static void main(String argv[]) {
    int a[][] = {{1, 0, 0}, {1, 1, 1}, {0, 1, 0}};
    BMatrix A = new BMatrix(a);
  }

The Whole Class

<<BMatrix.java>>=
public class BMatrix {
  Constructor
  Getter
  Setter
  Equals
  Negate
  Add
  Subtract
  Multiply
  Inverse
  Transpose
  String_representation
  Test
  Data
}