Binary matrix (Java)

This program is under development.
is complete, remove the {{develop}} tag.

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

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);
}
}
}
}
```

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>>=
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());
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 AT.

```<<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