Matrix Multiplication

A matrix is a rectangular table representing linear transformations or relationships between state coordinates. Multiplication composes compatible transformations and counts weighted transitions. Unlike elementwise multiplication, a matrix product uses a sum of row–column products. We implement the standard modular algorithm for an r×k matrix times a k×c matrix, making dimensions, order and numeric reductions explicit.

Prerequisites: Arrays; summation; modular arithmetic.

Build the idea

1. 1. Match the inner dimensions

   If A has r rows and k columns and B has k rows and c columns, AB has r rows and c columns. The shared k dimension is summed out. If these inner dimensions do not match, this ordinary product is undefined. Transposing or swapping operands does not automatically fix the intended transformation.

   $$C_{ij}=\sum _{t=0}^{k-1}{A}_{it}{B}_{tj}$$

2. 2. Derive entries from composition

   For a column vector v, Bv first combines input coordinates; A(Bv) then combines those results. Expanding the nested sums shows A(Bv)=(AB)v with the stated row–column formula. Thus AB applies B first, then A under the column-vector convention. Matrix multiplication is associative but generally NOT commutative, so A and B cannot be exchanged arbitrarily.

3. 3. Trace one rectangular product

   Multiply [[1,2,3],[4,5,6]] by [[7,8],[9,10],[11,12]]. Top-left is 1·7+2·9+3·11=58; top-right is 1·8+2·10+3·12=64. The second row yields 139 and154. Every output entry sums three products; it is not obtained by multiplying matching positions.

4. 4. Implement a safe modular accumulator

   Normalize entries modulo the fixed 1000000007. Loop i over output rows, k over the shared dimension, and j over output columns. Reduce c[i][j] after each contribution. Two reduced residues have product below about 10^18, and adding one reduced accumulator fits long long. Accumulating all k products before reduction could overflow even when each product fits.

5. 5. Define an identity for square matrices

   The k×k identity has ones on the diagonal and zeros elsewhere; AI=IA=A. This supplies the zero-power base for exponentiation. In graph counting, powers of an adjacency matrix count fixed-length walks when arithmetic matches the required count/modulus. Zero-one adjacency entries alone do not make powers represent only simple paths.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Define an identity for square matrices The k×k identity has ones on the diagonal and
// zeros elsewhere; AI=IA=A.
#include<iostream>
#include<vector>
using ll=long long;
int main(){
    int rows,inner,cols;
    std::cin>>rows>>inner>>cols;
    const ll MOD=1000000007;
    std::vector<std::vector<ll>>a(rows,std::vector<ll>(inner)),b(inner,std::vector<ll>(cols)),
        c(rows,std::vector<ll>(cols,0));
    for(auto&row:a){
        for(auto&x:row){
            std::cin>>x;
            x=(x%MOD+MOD)%MOD;
        }
    }
    for(auto&row:b){
        for(auto&x:row){
            std::cin>>x;
            x=(x%MOD+MOD)%MOD;
        }
    }
    for(int i=0;i<rows;++i){
        for(int k=0;k<inner;++k){
            for(int j=0;j<cols;++j){
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    for(const auto&row:c){
        for(int j=0;j<cols;++j){
            std::cout<<row[j]<<(j+1==cols?'\n':' ');
        }
    }
}

Complexity analysis

O(r·k·c) time and O(rk+kc+rc) total matrix storage; the output itself uses O(rc) extra space. Square n×n multiplication is O(n³). Dimensions are 1..100, input entries |value|≤10^9 and arithmetic is modulo 1000000007. These are standard multiplication bounds, not fast-matrix algorithms.

Example input and output

Read rows inner cols (1..100), then matrix A with rows×inner entries and B with inner×cols entries, |value|≤10^9. Print AB modulo 1000000007.

Input

2 3 2
1 2 3
4 5 6
7 8
9 10
11 12

Output

58 64
139 154

Each output is a row–column dot product; for example 4·7+5·9+6·11=139.

Practical applications

Use for linear transformations, transition composition, walk counts and DP recurrences with a fixed state dimension. For one transition, a direct vector update may be cheaper. Repeating the same square transformation many times motivates matrix exponentiation.

Check your understanding

Under column-vector conventions, what does AB apply first?

Put it into practice

Construct a square identity and test AI=IA=A.