Linear Algebra & FFT for Competitive Programming

A rectangular array of numbers with r rows and c columns, called an r×c matrix. The entry in row i and column j is written A[i][j] or a_ij. A square matrix has r = c.

Two matrices of the same dimensions are added entrywise: (A + B)[i][j] = A[i][j] + B[i][j]. Addition is commutative and associative.

If A is m×n and B is n×p, then C = A·B is m×p with C[i][j] = ∑ over k of A[i][k]·B[k][j]. The inner dimensions must match.

Matrix multiplication satisfies (AB)C = A(BC) but in general AB ≠ BA. Associativity is what lets matrix exponentiation use repeated squaring.

Multiplying two n×n matrices with the triple-loop definition costs Θ(n³) scalar multiplications. Strassen's algorithm lowers this to about Θ(n^2.81), but is rarely needed in CP.

The n×n identity I has 1 on the main diagonal and 0 elsewhere. It satisfies A·I = I·A = A and serves as the result of A⁰ in matrix exponentiation.