Multiply a Square Matrix by Itself
Problem
A square matrix A is given. Print A times A (the matrix product). The cell (i, j) of the result is the sum over k of A[i][k] * A[k][j]. Input: n and n, then the matrix. Print n rows.
Constraints
- 1 <= n <= 20
- |a[i][j]| <= 100
Examples
Input
2 2 1 2 3 4
Output
7 10 15 22
Solutions
Each result cell needs n multiplications, and there are n * n cells, so O(n^3). The loop order i, j, k follows the definition directly.
/*
* Problem : Matrix square.
* Input : n, n, then the matrix.
* Output : n rows.
* Approach: Dot products.
* Time : O(n^3)
* Space : O(n^2)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(int[][] m) {
// Step 1: Result cell (i, j) is the dot product of row i of A and column j of A.
int n = m.length;
String[] lines = new String[n];
for (int i = 0; i < n; i++) {
StringBuilder row = new StringBuilder();
for (int j = 0; j < n; j++) {
long sum = 0;
for (int k = 0; k < n; k++) {
sum += (long) m[i][k] * m[k][j];
}
row.append(j == 0 ? "" : " ").append(sum);
}
lines[i] = row.toString();
}
return lines;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int rows = scanner.nextInt();
int cols = scanner.nextInt();
int[][] m = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
m[i][j] = scanner.nextInt();
}
}
System.out.println(String.join("\n", solve(m)));
}
}
Hints (2)
- How many cells does the result have?
- Which row and column make cell (1, 0)?