Compute Prefix Matrix Products
Given an ordered sequence of square integer matrices with the same dimensions, return every left-to-right prefix product. The first result is the first matrix, and each later result multiplies the preceding prefix product by the next input matrix.
Function Signature
prefix_matrix_products(matrices: list[list[list[int]]]) -> list[list[list[int]]]
Valid Input Domain
The input may be empty. Otherwise every matrix is a nonempty d by d integer matrix with the same d. Valid inputs are guaranteed to keep every intermediate and final entry within signed 64-bit range.
Exact Output Semantics
Return an empty list for empty input. For matrices A0 through An-1, output P0 through Pn-1 in order, where P0 = A0 and Pi = Pi-1 multiplied by Ai using standard row-by-column matrix multiplication. Matrix and row ordering are preserved exactly.
Constraints
-
0 <= matrices.length <= 100.
-
1 <= d <= 20.
-
-1,000 <= matrix entry <= 1,000.
-
All intermediate results fit in signed 64-bit integers.
Public Examples
Example 1
Input: matrices = [[[1, 2], [0, 1]], [[2, 0], [1, 3]]]
Output: [[[1, 2], [0, 1]], [[4, 6], [1, 3]]]
The second prefix is the first matrix multiplied on the right by the second.
Example 2
Input: matrices = [[[2]], [[-3]], [[4]]]
Output: [[[2]], [[-6]], [[-24]]]
For one-by-one matrices, prefix products reduce to cumulative scalar multiplication.
Hints
-
Matrix multiplication order matters; do not reverse the new matrix and the accumulated prefix.
-
Each output must be a distinct matrix value even if internal buffers are reused.