Part IX · Number Theory, Combinatorics and Algebra
56. Matrices, Linear Algebra and Recurrences
6 lessons•24 topics•Intermediate / Expert
0 of 6 lessons published
56.01Outline
Matrix basics
- Vectors
- Matrix multiplication
- Identity matrix
- Transpose
- Determinants introduction
56.02Outline
Matrix exponentiation
- Fast powering
- Fibonacci matrix
- Linear recurrence transitions
- State transition matrices
56.03Outline
Linear recurrences
- Homogeneous recurrence
- Characteristic polynomial
- Kitamasa algorithm overview
56.04Outline
Systems of equations
- Gaussian elimination
- Pivoting
- Rank
- Modulo prime elimination
- XOR basis elimination
56.05Outline
Linear basis
- Basis over GF(2)
- Maximum subset XOR
- Representation queries
- Insert into XOR basis
56.06Outline
Graph algebra
- Adjacency matrix powers
- Path counting
- Transitive closure via Boolean algebra