Shared-Factor Kronecker-Sum LU and Tensor-Product Structured Matrices

Abstract

This paper establishes an exact LU theory for finite low-separation-rank Kronecker sums in arbitrary tensor dimension. The principal theorem treats matrices of the form M = ∑ᵣᵥ₌₁ ⊗ᵈₛ₌₁ Aᵥ,ₛ, where each mode shares fixed unit-triangular outer factors, Aᵥ,ₛ = LₛTᵥ,ₛUₛ, and the term-dependent cores Tᵥ,ₛ are upper triangular. The complete sum then has the exact normalized factorization M = (⊗ᵈₛ₌₁ Lₛ) C (⊗ᵈₛ₌₁ Uₛ), with C = ∑ᵣᵥ₌₁ ⊗ᵈₛ₌₁ Tᵥ,ₛ again upper triangular. Thus finite Kronecker sums of arbitrary separation rank remain exactly LU-factorable whenever their tensor factors possess common triangular bases. The tensor pivot at multi-index i = (i₁,…,i_d) is explicitly δᵢ = ∑ᵣᵥ₌₁ ∏ᵈₛ₌₁ tᵥ,ₛ,ᵢₛ. Over a field, the resulting normalized LU factorization is unique exactly when every proper tensor pivot is nonzero. The matrix is nonsingular exactly when every δᵢ ≠ 0, in which case det M = ∏ᵢ δᵢ, and the inverse is obtained directly from the shared triangular factors and C⁻¹. The previously treated shared-diagonal-core problem is recovered as the specialization in which every Tᵥ,ₛ is diagonal. The paper develops a broader tensor-product transfer theory around this result. Kronecker products inherit LU factorizations under explicit scalar-order hypotheses over associative rings, while over fields normalized tensor LU uniqueness is characterized by a sharp proper-pivot criterion. Integral diagonal equivalences likewise tensorize, transferring diagonal reductions from structured one-dimensional families to arbitrary tensor products. Further results give exact bivariate and k-dimensional row-sum generating laws, falling-factorial inverse transforms, tensor-grid polynomial interpolation identities, spectral conditioning formulas, separable recurrence operators, the exact Neumann solvability criterion for multiplicative coupling, and boundary-series generating functions for finite-stencil recurrences. Ordered Kronecker contractions and structured linear-system solvers yield explicit arithmetic and storage complexity formulas that distinguish implicit tensor representations from fully materialized matrices. The final part connects the theory with low-rank tensor computation and scientific computing. It gives the rearrangement/SVD characterization of optimal Frobenius-norm Kronecker approximation, exact Gaussian-binomial lattice-path interleavings, and tensor-train or matrix-product-operator representations of finite Kronecker sums. An r-term k-fold Kronecker sum admits an exact tensor-train representation with internal bond dimensions at most r, while over fields the minimum possible bond dimensions are exactly the corresponding unfolding ranks. Separable differential operators on tensor grids are represented exactly by finite Kronecker sums, yielding separated spectral solution formulas for classes of partial-difference and higher-order differential discretizations. The results provide a unified algebraic framework for shared-factor Kronecker-sum LU factorization, structured tensor transforms, low-separation-rank representations, interpolation, recurrence systems, and separable numerical operators.