Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds

1 Introduction

• Existing bounds leave a gap: the O(n1.447) upper bound exceeds the Ω(nω−1) lower bound, and even ideal rectangular multiplication leaves an O(n1+1/3) upper bound against Ω(n).The paper also asks whether algebraic techniques can yield faster algorithms, potentially with linear update time.Source: §1 · p. 3

1.1 Our Algorithmic Results (Details in Sections 4 and 6 and appendix C)

• O(n1.407) time per entry update and entry query, and O(n1.529) per column update and row query, are the paper’s two improved standard-setting bounds.The first improves on Sankowski’s O(n1.447) bound and implies faster algorithms for over 10 problems; the second gives first non-trivial bounds for column-update versions of largest eigenvalue, rank, and determinant.Source: §1.1 · p. 4
• Knowing updated columns ahead of time, without their new values, supports faster look-ahead algorithms; with n future columns known, update time is O(nω−1).For online bipartite matching, the column-incremental case gives O(nω) total time, improving O(m√n) when the graph is dense and matching the static bound.Source: §1.1 · p. 5
• Maintaining the inverse of a transformation matrix lets the algorithm answer queries using A−1 = T−1(A′)−1, with periodic resets that use fast matrix multiplication.The new implicit-update algorithm maintains T2 implicitly, allowing the approach to be repeated one more time without the cost of maintaining T2 explicitly.Source: §1.1 · p. 5

1.2 Our Conditional Lower Bounds (Details in Section 5)

• Variants of the OMv conjecture yield tight conditional lower bounds for dynamic matrix inverse and applications including matching, st-reachability, cycle detection, and DAG path counting.The paper’s conjectures also match some bounds even if faster matrix multiplication algorithms are found.Source: §1.2 · p. 7

1.3 Other Related Work

• The look-ahead algorithms require only advance knowledge of which columns will be updated, not their new values, unlike earlier algorithms that needed more information.The paper compares these algorithms with previous look-ahead results by.Source: §1.3 · p. 8
• The column-incremental rank algorithm maintains bipartite maximum matching size under one-side node arrivals in O(nω) total time, improving O(m√n) when dense and matching the static bound.The earlier algorithm needed new values ahead of time, while handled only element updates.Source: §1.3 · p. 8

Reduction to Transformation Inverse Maintenance

• The overview focuses on invertible matrices and element updates; a reduction extends the algorithm to cases where A(t) may become singular.The same ideas are stated to extend to other update and query variants.Source: §2 · p. 9

Previous maintenance of (T (0,t ))−1

• Sankowski’s second algorithm represents the inverse as a chain of sparse transformation inverses, but that sparsity makes fast matrix multiplication difficult to exploit.The overview identifies using fast matrix multiplication to maintain the transformation inverse as the new aspect of its algorithm.Source: §2 · pp. 10–11

Reduction to Transformation Inverse Maintenance

• Explicitly maintaining T(t′,t) is too costly because each update requires a matrix-vector product with (T(0,t′))^-1.With repeated resets, this approach incurs an Ω(nt) lower bound per update, giving no improvement over Sankowski’s first algorithm.Source: §2 · p. 11

Implicit input, simplification and generalization of Sankowski’s second algorithm

• The implicit-update subroutine tracks the C1 block and queries needed rows of C2, avoiding the need to know all of T(t′,t).It uses O(t−t′) oracle queries per operation and has O((t−t′)^2) update and query time.Source: §2 · pp. 11–12

Summary

• The algorithm maintains A(0), T(0,t′), and an update matrix S(t′,t), while a subroutine maintains (T(t′,t))^-1 under implicit updates.The inverse of A(t) is assembled from these transformation inverses and (A(0))^-1; row queries use the implicit-inverse subroutine.Source: §2 · p. 12

Back to maintaining (T (0,t))−1

• When t−t′ grows, the algorithm resets the transformation and uses fast matrix multiplication to combine dense matrices.The reset computes T(0,t)=T(0,t′)T(t′,t); a further reset can make A(t) the new A(0).Source: §2 · pp. 11–13

Notation: Identity and Submatrices

• The notation A_I,J denotes the submatrix with row indices I and column indices J; vectors of indices preserve their listed order.The paper also uses u⊺v for inner products and uv⊺ for outer products.Source: §3 · p. 13

Fast Matrix Multiplication

• The paper uses O(n^ω) for multiplying square matrices and states that multiplication, inversion, determinant, and rank have the same complexity.Algorithm complexity depends on matrix multiplication and inversion costs; the overview cites a then-current bound of ω < 2.3728639.Source: §3 · p. 13

Transformation Matrices

• A transformation matrix has form T=I+C, where C has few non-zero columns; row and column permutations expose a block form for T and its inverse.The inverse’s blocks include an identity block and a block determined by the inverse of C1.Source: §3 · pp. 13, 16
• For a set J with |J|=n^δ, T^-1 can be computed in O(n^ω(1,δ,δ)) field operations; given I⊂[n] with J⊂I and |I|=n^ε, rows I of T^-1 require O(n^ω(ε,δ,δ)) operations, using only rows I of T.Source: §3 · p. 16
• For A=I+C and B=I+N with n^a and n^b non-zero columns, respectively, AB takes O(n^ω(1,a,b)) operations and has non-identity columns only in their union.Computing selected rows can use O(n^ω(c,a,b)) operations when |I|=n^c, requiring only specified rows of N.Source: §3 · p. 16

4 Dynamic Matrix Inverse

• Column updates cost O(n^(1+ε)+n^(ω(1,1,ε)-ε)) and row queries O(n^(1+ε)); balanced update/query costs are O(n^1.529) at current ω and O(n^1.5) when ω=2.The balanced current-ω choice is ε≈0.723; for ω=2, ε=0.5.Source: §4 · p. 17
• Entry updates cost O(n^(ε2+ε1)+n^(ω(1,ε1,ε2)-ε1)+n^(ω(1,1,ε2)-ε2)) and inverse-entry queries O(n^(ε2+ε1)); balanced costs are O(n^1.407) at current ω and O(n^1.25) when ω=2.The balancing choices are ε1≈0.551, ε2≈0.855 for current ω, and ε1=0.5, ε2=0.75 for ω=2.Source: §4 · p. 17

4.1 Transformation Maintenance implies Dynamic Matrix Inverse

• Theorem 4.3 reduces entry-update inversion to transformation maintenance: for k≤n^ε updates, the update cost is O(u(k,n^ε)+(kn^-ε)·(p+n^ω(1,1,ε))), while an n^δ1×n^δ2 inverse submatrix query costs O(q(n^δ1,n^ε)+n^ω(δ1,ε,δ2)).The reduction represents A(t)=A(0)T(0,t), converts entry changes to column updates of T, and resets after n^ε changed entries.Source: §4.1 · pp. 17–18

4.2 Explicit Transformation Maintenance

• For T=I+N with at most n^ε1 nonzero columns in N and n^ε0 changed columns in C, Lemma 4.6 updates a known inverse after T becomes T+C in O(n^ω(1,ε1,ε0)) operations.When ε0=0, the complexity simplifies to O(n^(1+ε1)).Source: §4.2 · p. 19

4.3 Implicit Transformation Maintenance

• For implicitly represented B(t), Lemma 4.7 maintains inverse rows with update cost O(n^ω(ε1,ε1,ε0)) and query cost O(n^ω(δ,ε1,ε1)) for n^δ queried rows, using submatrix queries to the data structure.The algorithm requires no preprocessing.Source: §4.3 · pp. 20–21
• Implicit transformation maintenance tracks the accumulated updated index set I(t) and an auxiliary M(t) matching B(t) on I(t) × I(t), together with M(t)^−1.Source: §4.3 · p. 22

4.4 Combining the Transformation Maintenance Algorithms

• When B(t)=I+C(t) has at most n^ε2 nonzero columns, Lemma 4.9 supports column updates and submatrix inverse queries with the stated fast-matrix-multiplication bounds.Update time is O(n^ω(ε2,ε1,ε0) + n^ω(1,ε2,ε1)−ε1+ε0); query time is O(n^ω(δ1,ε2,ε1) + n^ω(δ1,min{ε2,δ2},ε1)). Preprocessing takes O(n^ω), or none when B(0)=I.Source: §4.4 · p. 23
• Theorem 4.3 converts transformation-inverse maintenance into an element-update dynamic matrix-inverse algorithm, with update time O(u(n^ε0,n^ε2) + (n^−ε2+ε0) ⋅ (p + n^ω(1,1,ε2))).With the Lemma 4.9 update bound and ε0=0, Theorem 4.2 has update complexity O(n^ε2+ε1 + n^ω(1,ε1,ε2)−ε1 + n^ω(1,1,ε2)−ε2).Source: §4.4 · p. 23

4.5 Applications

• Dynamic matrix inverse, adjoint, determinant, and linear-system solving are equivalent under black-box reductions that preserve update time.Source: §4.5 · p. 27
• Maximum bipartite matching size is maintainable in O(n^1.529) when node updates affect only one side; triangle detection and st-reachability attain O(n^1.529) when updates change only outgoing edges.Source: §4.5 · p. 27

5.1 Column Update, Row Query

• The v-hinted Mv conjecture extends OMv by revealing a set of possible vectors first and selecting one later, yielding a trade-off between precomputation and online matrix-vector work.The resulting conditional bound also applies to dynamic transitive closure with restricted incoming-edge updates and source-reachability queries.Source: §5.1 · pp. 28–30
• Under the v-hinted Mv conjecture, column-update, row-query dynamic matrix inverse and adjoint require worst-case update time Ω(n^(ω(1,1,τ)-τ-ε)) when query time is O(n^(1+τ-ε)).For current ω, balancing update and query time gives a lower bound of Ω(n^1.528); the bound is tight with the paper’s upper bound when query time is not larger than update time.Source: §5.1 · pp. 29–30

5.2 Element Update, Row Query

• Under the Mv-hinted Mv conjecture, element-update, row-query dynamic matrix inverse and adjoint require worst-case update time Ω(n^(ω(1,1,τ)-τ-ε)) when query time is O(n^(1+τ-ε)).For current ω, the balanced lower bound is Ω(n^1.528); for element queries, the update lower bound holds when query time is O(n^(τ-ε)).Source: §5.2 · p. 32
• The same conjecture yields lower bounds for dynamic transitive closure and DAG-path counting with edge updates and source queries, and for pair queries under a faster-query condition.For source queries, the update lower bound is Ω(n^(ω(1,1,τ)-τ-ε)) when query time is O(n^(1+τ-ε)); for pair queries, the query-time condition is O(n^(τ-ε)).Source: §5.2 · p. 32

5.3 Element Update, Element Query

• The uMv-hinted uMv problem [HKN+15] addresses the column-query look-ahead in the prior setup by using hints for vectors and a matrix, then asking for one product value.Its phases choose indices I and J to construct the hinted matrix and then query a single entry.Source: §5.3 · pp. 32–33
• The lower-bound conjectures formalize a trade-off between precomputing all possibilities and waiting to compute only requested information, a barrier for currently known dynamic matrix-inverse techniques.They ask whether a better third option exists.Source: §5.3 · p. 34, §5.4 · p. 35
• Assuming Conjecture 5.12, dynamic 5-matrix product requires Ω(min_{τ1,τ2}(n^(τ1+τ2)+n^(ω(1,τ1,τ2)−τ2)+n^(ω(1,1,τ1)−τ1))n^−ε) worst-case update or query time.This applies with polynomial-time preprocessing and for all ε > 0.Source: §5.3 · p. 34
• The same conditional bound applies to dynamic transitive closure, DAG path counting, strong connectivity, k-path, cycle detection, and k-cycle detection.The algorithms use edge updates and pair queries; the corollary assumes polynomial-time preprocessing and applies for all ε > 0.Source: §5.3 · p. 34
• Assuming Conjecture 5.12, dynamic matrix inverse, adjoint, determinant, and rank require Ω((n^(τ1+τ2)+n^(ω(1,τ1,τ2)−τ2)+n^(ω(1,1,τ1)−τ1))n^−ε) worst-case update or query time.This lower bound assumes polynomial-time preprocessing and holds for all ε > 0.Source: §5.3 · pp. 34–35
• Assuming Conjecture 5.12, dynamic bipartite perfect matching with element updates and polynomial preprocessing requires Ω((n^(τ1+τ2)+n^(ω(1,τ1,τ2)−τ2)+n^(ω(1,1,τ1)−τ1))n^−ε) worst-case update time.The bound holds for all ε > 0.Source: §5.3 · p. 35

5.4 Discussion on Super-Linear Bounds for Dynamic Matrix Inverse

• For element updates, encoding all n vectors requires Ω(n^(2−ε)) total updates for every constant ε > 0, precluding super-linear lower bounds; column-update/row-query reductions require n updates or one update and n queries.For every constant ε > 0, multiphase requires O(n^(1−ε)) element updates just to insert v, so it cannot yield super-linear lower bounds.Source: §5.4 · p. 35
• A triangle-detection reduction can give an amortized n^(ω−1) lower bound only with o(n^ω) preprocessing, which does not rule out fast-update algorithms using Ω(n^ω) preprocessing.For example, dynamic determinant with o(n^ω) preprocessing already requires Ω(n^ω) update time.Source: §5.4 · p. 36
• APSP reductions are unsuitable for algebraic algorithms because they incur pseudo-polynomial dependence on edge weights, while BMM rules out fast matrix multiplication.Source: §5.4 · p. 36

6 Look-Ahead Setting

• O(n^ω) total time suffices to maintain determinant and rank as matrix columns change left to right, with each new column’s values revealed only after the answer.The look-ahead need not provide update values; the section also allows rough estimates of future update and query indices.Source: §6 · p. 37
• O(n^ω) total time suffices to maintain maximum matching size as right-side nodes are added one by one, with each addition following the current answer.The theorem also directly implies the same total-time upper bound for online bipartite matching.Source: §6 · p. 37

6.1 Short Sequence of Updates

• For the first n^ε rounds, an s-accurate n^ε-look-ahead supports column updates and inverse row queries in O(n^(ω(ε,δ,ε)-ε)) time per operation.The look-ahead concerns possible update and query locations, not update values.Source: §6.1 · p. 39
• The short-sequence algorithm maintains logarithmically many inverse copies, updates each at a different interval, and spreads computations across rounds to obtain a worst-case bound.Each copy maintains only a subset of inverse rows.Source: §6.1 · p. 40
• For up to n^ε rounds, s-accurate n^ε-look-ahead supports column updates and row queries in O(n^ω(ε,δ,ε)−ε) operations each, assuming T(0)=I+N has at most n^δ nonzero columns.The worst-case cost is simplified to O(n^ω(ε,ε,δ)−ε), with an additional log n factor if matrix multiplication has linear complexity.Source: §6.1 · p. 41

6.2 Long Sequence of Updates

• For longer sequences with at most n^ε2 nonzero columns, s-accurate n^ε0-look-ahead supports column updates and row queries in O(n^ω(ε2,ε1,ε0)−ε0 + n^ω(1,ε2,ε2)−ε1) operations each.The algorithm combines batch updates every n^ε0 rounds with the short-sequence look-ahead algorithm; the average update bound can be made worst-case.Source: §6.2 · p. 43
• With s-accurate n^ε0-look-ahead, column updates and row queries take O(n^ω(1,ε1,ε0)−ε0 + n^ω(1,1,ε1)−ε1) operations; Ω(n)-look-ahead gives O(n^ω−1), while O(1)-look-ahead matches the non-look-ahead algorithm.The paper states the Ω(n)-look-ahead bound is optimal because it can be used to invert an entire matrix.Source: §6.2 · p. 43
• For element updates and queries, s-accurate n^ε0-look-ahead gives O(n^ω(ε2,ε1,ε0)−ε0 + n^ω(1,ε2,ε1)−ε1 + n^ω(1,1,ε2)−ε1) operations.At Ω(n)-look-ahead the complexity is O(n^ω−1), which the paper says is optimal in the sense that an improvement would yield a faster matrix-rank algorithm for sparse matrices; current algorithms can require Ω(n^ω−1) operations [CKL13]. O(1)-look-ahead matches the non-look-ahead upper and lower bounds.Source: §6.2 · pp. 43–44

Amortization

• Faster amortized updates remain open, as do reasonable conjectures giving lower bounds for amortized update time.The paper notes that amortization might improve update time for applications such as st-reachability.Source: §7 · p. 44

Refuting or supporting our conjectures

• The new conjectures need scrutiny: breaking one could offer hope for improved algorithms, while algebraic circuit lower bounds might support them.Source: §7 · p. 44

Distances

• For st-distance and all-pairs distances, the best lower bound comes from reachability, while the upper bound remains far higher.Closing or narrowing this gap is an open problem.Source: §7 · p. 44
• Extending the results to weighted graphs is open beyond small integer weights: the stated extension to weights in [1,W] costs an extra W factor.The paper asks whether a logW dependence is possible, for example through approximation as in.Source: §7 · p. 44

Maintaining the object

• Algebraic techniques often return only a quantitative answer, leaving open whether the maintained object itself, such as a matching or path, can be recovered.For online bipartite matching, the algorithm does not identify which left nodes are matched or which edges are used.Source: §7 · p. 45

Sparse graphs

• For sparse graphs, dynamic matrix inverse gives the only non-trivial st-reachability upper bound, but it is slower than O(m) search.The paper asks whether an O(m^(1−ε)) upper bound or an Ω(m) conditional lower bound is possible; the cited lower bound is Ω(m^0.814) with O(m^1.407) preprocessing [AW14].Source: §7 · p. 45

Derandomization

• Derandomization remains open for applications such as reachability, since extending the non-singular-matrix result to temporarily singular matrices requires randomization.The paper also asks whether such applications can be made Las Vegas rather than Monte Carlo.Source: §7 · p. 45

A Runtime Analysis, Balancing Terms

• The matrix multiplication exponent ω is the infimum exponent for multiplying two n × n matrices in O(n^s) arithmetic operations, with the stated bound ω < 2.3728639 [Gal14].The text notes that O(n^ω) conventionally suppresses the technically required ε term.Source: A Runtime Analysis, Balancing Terms · p. 46
• Rectangular multiplication exponents are reduced to bounds for ω(1,1,k), and a small optimization program selects parameters minimizing the resulting runtime expressions.For Theorem 4.1, the example minimizes max{1+ε, ω(1,1,ε)−ε} over 0≤ε≤1.Source: A Runtime Analysis, Balancing Terms · p. 46

B Worst-Case Standard Technique

• For reset time O(r), update time O(u(t)), and query time O(q(t)), the standard technique yields worst-case update O(u(μ)+r/μ) and query O(q(μ)).Source: B Worst-Case Standard Technique · p. 46
• Two phase-shifted copies make one algorithm copy available while the other resets and catches up; the technique is nontrivial for worst-case rather than amortized guarantees.Each copy alternates between reset-and-catch-up and a μ/2-round available phase.Source: B Worst-Case Standard Technique · pp. 46–47

C Applications

• Figure 9 uses arrows to indicate that an algorithm for one problem can solve another, and separates algebraic applications from graph-problem reductions.The algebraic applications are covered in subsection C.1, reductions in the green box in C.2, and remaining graph reductions in C.3.Source: Figure 9 · p. 47, C Applications · p. 47
• Many graph applications use existing reductions to dynamic algebraic problems such as dynamic rank or determinant, so the section first explains how dynamic matrix inverse algorithms support those problems.Source: C Applications · p. 48

• Dynamic matrix inverse supports products of arbitrarily many matrices, including queries for consecutive subproducts, with corresponding update, query, and preprocessing costs at dimension k.For matrices A_i of dimensions n_i × m_i, k = sum_i(n_i + m_i); the costs are O(u(k)), O(q(k)), and O(p(k)), respectively.Source: §C.1 · p. 48
• For nonsingular matrices, inverse and determinant admit black-box reductions in both directions; inverse-to-determinant updates cost O(u(n) + q(n)) for element or column updates.The determinant reduction preprocesses in O(p(n) + n^ω); conversely, determinant updates yield inverse element queries in O(u(n)) with O(p(n)) preprocessing. The inverse-to-determinant reduction is described as the first black-box reduction between them.Source: §C.1 · pp. 48–49
• For nonsingular matrices, dynamic inverse and adjoint are equivalent for element-update/element-query and column-update/row-query operations.The reductions use the relation adj(A) = det(A)A−1 and track determinant changes multiplicatively or adjoint changes additively.Source: §C.1 · pp. 49–50
• Dynamic inverse supports maintaining A−1M, and element-update/element-query inverse maintenance is equivalent to dynamic linear-system solving.Using a column-update/row-query inverse algorithm also maintains explicit solutions to Ax = b when entire constraints are replaced; linear-system algorithms further yield dynamic interpolation polynomials with the same update and query complexity.Source: §C.1 · p. 50
• For m > n and rank-n matrices, dynamic inverse yields a dynamic pseudo-inverse algorithm supporting row scaling updates in O(u(m)) and queries in O(q(m)).Preprocessing takes O(p(m)); the matrix must remain rank n throughout updates.Source: §C.1 · p. 51
• With k = O(ε−1 · log n ε−1), dynamic matrix products maintain the largest absolute eigenvalue within error ε for symmetric matrices over an ordered field.Updates cost O(k · u(n,k) + q(n,k)); when row queries are supported, a vector v satisfying (v⊺Av)/v⊺v ≥ (1 − ε)λ1 can be queried in O(q(n,k)). The singular-value variant uses element updates to A.Source: §C.1 · p. 51
• A randomized determinant reduction maintains matrix rank even when the matrix becomes singular, with high probability, using O(u(3n)) updates and O(p(3n) + (3n)^ω) preprocessing [San07, Corollary 4.1].In the look-ahead adaptation, after t updates to A, updates to the auxiliary I(k) block use column indices in {k−t, ..., k+t}, enabling the weaker look-ahead setting.Source: §C.1 · pp. 51–52
• A dynamic inverse algorithm can explicitly maintain A−1_H,H with update cost O(u(|H|,n) + q(|H|,n) + |H|^2), enabling applications including ST-reachability bounds.The same explicit-submatrix technique supports a hitting-set argument for reducing all-pairs shortest distances to dynamic matrix inverse.Source: §C.1 · pp. 52–53

C.1 Algebraic Applications

• Corollary C.12 supports entry updates, inverse-entry queries, and O(1)-time queries for entries in (A^-1)_H,H, after O(n^ω) preprocessing.For |H| = O(n^(1−μ)) and 0 ≤ ε1 ≤ ε2 ≤ 1, update time is O(n^(ε2+ε1) + n^(ω(1,ε1,ε2)−ε1) + n^(ω(1,1,ε2)−ε2) + n^(ε2+1−μ) + n^(2−2μ)); arbitrary inverse-entry queries take O(n^(ε2+ε1)).Source: §C.1 · pp. 53–54
• O(n^1.407) update time is achievable when 1−μ ≤ 0.55 with current ω; if ω = 2, the complexity is O(n^1.25) for 1−μ ≤ 0.5.The first bound matches Theorem 4.2 while providing faster queries for some submatrix.Source: §C.1 · p. 54
• The transitive-closure reduction and Corollary C.12 imply an O(n^1.407) algorithm for ST-reachability when |S|, |T| = O(√n).Source: §C.1 · p. 54

C.2 Polynomial Matrices

• Dynamic matrix-inverse algorithms maintain the inverse of I − X · A modulo X^m with updates to A, at an O~(m) increase in ring operations.The same polynomial-matrix extension supports maintaining the determinant or adjoint of I − X · A.Source: §C.2 · pp. 54, 56
• Inverses of matrices of the form I − X · M can be computed modulo X^m using a truncated geometric series, avoiding polynomial division.The section applies this approach to matrices that dynamic algorithms need to invert over R[X]/⟨X^m⟩.Source: §C.2 · p. 54
• Polynomial matrix inversion modulo X^m takes O~(m n^ω) time, an O~(m) slowdown over matrix inversion.The degree bound makes each matrix product cost O(m log m) operations.Source: §C.2 · p. 54
• The polynomial extension supports maintaining the determinant or adjoint of I − X · A with updates to A, increasing ring operations by O~(m).Source: §C.2 · p. 56
• The algorithms also maintain the determinant and adjoint of general matrices over rings without division, with an O~(n) increase in ring operations.The construction uses polynomial matrices evaluated at X = 1.Source: §C.2 · p. 56

Reachability

• A dynamic adjoint algorithm yields randomized transitive closure with the same preprocessing, update, and query costs as its matrix algorithm.Incoming-edge-only node updates with source queries admit O(n1.529) time, whereas outgoing-edge-only node updates with source queries have an Ω(n2−ε) lower bound for all ε > 0 [HKN+15].Source: §C.3 · p. 57

Other graph applications

• Dynamic single-source reachability yields strong connectivity; dynamic inverse and determinant algorithms yield DAG path counting [San04, Theorem 5] and spanning-tree counting [San04, Corollary 1].Strong-connectivity updates take O(u(n)+ q(n)); DAG path-counting updates and queries take O(u(n)) and O(q(n)); spanning-tree edge updates take O(u(n)); each uses O(p(n)) preprocessing.Source: §C.3 · pp. 57–58

Triangle detection

• Five-matrix products support subgraph triangle detection under node on/off updates, while three-matrix products support triangle detection under incoming-edge-only node updates; both use O(u(n)+q(n)) updates and O(p(n) + n ⋅q(n)) preprocessing.The product algorithms respectively require element updates and queries, or column updates and element queries.Source: §C.3 · p. 58

Cycle detection

• A dynamic determinant algorithm yields randomized cycle detection with O(u(n)) updates and O(p(n)) preprocessing, when its matrix remains nonsingular.The reduction tests whether det(A + I) − 1 is a zero polynomial using Schwartz-Zippel; the randomized matrix is invertible with high probability.Source: §C.3 · p. 59

Bipartite matching

• A dynamic rank algorithm yields randomized bipartite maximum-cardinality matching-size maintenance with O(u(n)) updates and O(p(n)) preprocessing.Element, column, and row updates correspond respectively to edge, right-node, and left-node updates.Source: §C.3 · pp. 59–60

k-path and k-cycle detection

• A dynamic k-matrix-product algorithm yields k-path detection with preprocessing O(f(k) ·p(k,n)), edge updates O(f(k) ·u(k,n)), and pair queries O(f(k)q(k,n)).Color coding and maintaining multiple randomized graphs extend k-walk detection to k-paths.Source: §C.3 · pp. 60–61
• A polynomial-matrix determinant algorithm yields randomized k-cycle detection with preprocessing O(f(k) ·p(k,n)) and edge updates O(f(k) ·u(k,n)).The reduction uses color coding and a polynomial matrix to limit detection to cycles of length k.Source: §C.3 · p. 61

C.3 Graph Applications

• For k-cycle detection, the kth-degree term of det(I−X·A) is nonzero with high probability exactly when the color-coded graph has a k-cycle, and independently color-coded graphs are maintained.The determinant encodes cycle decompositions; random field values prevent cancellation, and f(k) independent color codings yield high-probability detection.Source: §C.3 · p. 61
• Under the stated inverse-query and update assumptions, st-distance preprocessing takes O(p(n^µ,n)) and edge updates take ~O(u(n^µ,n) + q(n^µ,n) + n^(2−µ)).For any 0 ≤ µ ≤ 1, the theorem uses a uniformly random subset H of size ~O(n^(1−µ)).Source: §C.3 · p. 62
• For distances below m=n^µ, the smallest-degree monomial in (I−X·A)^−1 encodes distance, with random finite-field entries limiting coefficient bit-length to O(log n).The method randomizes nonzero entries over a field of size Θ(n^c); union bounding gives probability at least 1/n^(c−3) that all distances below m are encoded.Source: §C.3 · p. 62
• For longer distances, a random H of size ~O(n^(1−µ)) segments shortest paths into hops through H, enabling Dijkstra on a smaller weighted graph in O(n^(2(1−µ))) time.The resulting distance equals the original shortest distance with high probability, and the update time is ~O(u(n^µ,n) + q(n^µ,n) + n^(2−µ)).Source: §C.3 · p. 62

D Bit-Length Increase for the Matrix Product Reduction

• With input entries bounded by polylog(n), maintaining the inverse of the reduction matrix requires internal numbers of length O(poly(s) polylog(n)).The updates are restricted to the component matrices A1, ..., As.Source: D Bit-Length Increase for the Matrix… · p. 63
• For upper triangular block matrices with s blocks per row and column, inverse and product entries increase bit length by at most O(poly(s) · polylog(n)).The inverse blocks can be computed bottom up without circular dependencies, and products and inverses reduce to products of smaller n × n matrices.Source: D Bit-Length Increase for the Matrix… · pp. 63–64
• The algorithm represents the maintained inverse through a chain of transformation matrices, whose entries and inverse entries have bit length at most a poly(s) · polylog(n) factor larger than A's.The transformation matrices and their inverses remain upper triangular block matrices.Source: D Bit-Length Increase for the Matrix… · p. 64
• For the largest eigenvector reduction, s = polylog(n), so bit length affects the algorithm's time complexity only by polylogarithmic factors.Source: D Bit-Length Increase for the Matrix… · p. 64

E.1 Lower Bounds assuming o(nω) pre-processing

• Under the assumption that the static version requires Ω(n^ω) time, triangle detection, perfect matching, matrix rank, and matrix determinant require Ω(n^ω) update time if preprocessing is o(n^ω).Source: §E.1 · p. 64
• Changing one input entry, preprocessing on the modified input, then reverting the change with one update yields the static solution in o(n^ω) total time if both dynamic costs are o(n^ω).Source: §E.1 · p. 64
• With o(n^ω) preprocessing, the theorem rules out non-trivial worst-case update time for these problems.Source: §E.1 · p. 64

E.2 Implications of Mv and OMv results

• The lower bounds simplify dynamic matrix inverse to matrix-matrix and matrix-vector products, so prior Mv and OMv results can also apply to the new problems.Source: §E.2 · p. 64

Exploiting matrix-vector product algorithms

• Theorem E.2 improves the last phase of the hinted problems by a log n factor using faster matrix-vector multiplication.The cited result improves the final phase while leaving earlier phases to read and save the input.Source: Exploiting matrix-vector product… · pp. 64–65
• The later O(n^2/2^O(√n)) matrix-vector bound does not break the conjectures because its improvement is sub-polynomial, its bound is amortized, or worst-case conversion needs exponential preprocessing.The section also cites an earlier O(n^2/(ε log n)) algorithm after O(n^(2+ε)) preprocessing.Source: Exploiting matrix-vector product… · p. 65
• An algorithm breaking the Mv conjecture would also break the v-hinted Mv conjecture, since both allow polynomial preprocessing of the matrix.The stated reduction applies to Definition 5.1; the other hinted problems lack this reduction because their query-phase matrices are not known initially.Source: Exploiting matrix-vector product… · p. 65
• For the v-hinted Mv problem, splitting M into smaller square matrices yields a last-phase time of O(n^(1+τ−ε)) when the Mv algorithm beats its conjectured bound.The construction runs an Mv algorithm on each block and combines the outputs.Source: Exploiting matrix-vector product… · p. 65
• The cell-probe model admits polynomial-factor improvements to the trivial times, so the paper’s conjectures do not hold in that model.The cited cell-probe algorithm stores the matrix with O(n^(3/2)) additional bits and computes Mv in O(n^(3/2)) operations.Source: Exploiting matrix-vector product… · pp. 65–66
• The paper states no reduction to or from OMv for its hinted problems: OMv vectors arrive online, whereas these problems provide vector hints.OMv repeats the query phase online, with each vector supplied only after the preceding product is returned.Source: Exploiting matrix-vector product… · p. 66

E.3 OMv-based Lower Bounds

• Assuming OMv, dynamic k-matrix product, linear systems, determinant, inverse, adjoint, and rank require Ω(n^(3−ε)) time for every constant ε>0 over O(n) updates and queries.The theorem allows row and column updates and, for multiple maintained values, element queries.Source: §E.3 · p. 66
• The OuMv assumption requires Ω(n^(3−ε)) time for n online vector-pair queries after polynomial preprocessing, over the boolean semiring.The proof notes that the computations can instead be performed over a finite field Zp with p>n.Source: §E.3 · p. 66
• The proofs reduce k-matrix product to row updates and u⊺Mv queries, then derive inverse, adjoint, determinant, linear-system, and rank bounds through further reductions.The rank route passes through dynamic perfect bipartite matching with left and right node updates.Source: §E.3 · p. 66
• OMv implies Ω(n^(2−ε)) time per node update, or Ω(n^(1−ε)) per edge update, for the listed path, distance, and cycle problems.The listed problems include DAG path counting, counting s-t paths, all-pairs shortest distances, cycle detection, k-cycle detection, and k-path.Source: §E.3 · p. 67
• The graph lower bounds transfer from transitive closure and s-t reachability; a four-layer DAG encodes u⊺Mv, extending hardness to path counting and k-path, and adding an edge yields cycle hardness.The construction also gives hardness for k-cycle when k≥4.Source: §E.3 · p. 67

E.4 Amortized Lower Bounds

• These amortized bounds are exploratory rather than conjectures, and they do not hold under the fixed-start assumption used by many amortized dynamic graph algorithms.The appendix identifies finding clean amortized conjectures or breaking the upper bounds through amortization as open directions.Source: §E.4 · p. 67
• For every 0≤τ≤1, the reductions rule out simultaneously achieving amortized update time O(n^(ω(1,1,τ)−τ−ε)) and query time O(n^(1+τ−ε)).This bound follows for the repeated v-hinted Mv problem and its reductions.Source: §E.4 · pp. 67–68
• For uMv-hinted uMv, the appendix gives a separate amortized tradeoff: no algorithm can combine the stated update bound O(min{n^(ω(1,1,τ1)−τ1−ε), n^(ω(1,τ1,τ2)−τ2−ε)}) with query time O(n^(τ1+τ2−ε)).The appendix frames this as an amortized variant of the hinted problem.Source: §E.4 · p. 68

E.5 Column Update Induces Ω(nt) Changes in the Inverse

• A column update can change Ω(nt) entries of the inverse, so explicitly maintaining a matrix of this structure requires Ω(nt) worst-case update time.The section constructs a matrix differing from identity in t−1 columns before changing one further column.Source: §E.5 · p. 68