101. On the uniqueness and computation of commuting extensions.
- Author
-
Koiran, Pascal
- Subjects
- *
CUBATURE formulas , *LINEAR algebra , *QUANTUM theory , *NUMERICAL analysis , *QUANTUM mechanics - Abstract
A tuple (Z 1 , ... , Z p) of matrices of size r × r is said to be a commuting extension of a tuple (A 1 , ... , A p) of matrices of size n × n if the Z i pairwise commute and each A i sits in the upper left corner of a block decomposition of Z i (here, r and n are two arbitrary integers with n < r). This notion was discovered and rediscovered in several contexts including algebraic complexity theory (in Strassen's work on tensor rank), in numerical analysis for the construction of cubature formulas and in quantum mechanics for the study of computational methods and the study of the so-called "quantum Zeno dynamics." Commuting extensions have also attracted the attention of the linear algebra community. In this paper we present 3 types of results: (i) Theorems on the uniqueness of commuting extensions for three matrices or more. (ii) Algorithms for the computation of commuting extensions of minimal size. These algorithms work under the same assumptions as our uniqueness theorems. They are applicable up to r = 4 n / 3 , and are apparently the first provably efficient algorithms for this problem applicable beyond r = n + 1. (iii) A genericity theorem showing that our algorithms and uniqueness theorems can be applied to a wide range of input matrices. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF