On the uniqueness and computation of commuting extensions

A tuple (Z_1,...,Z_p) of matrices of size r is said to be a commuting extension of a tuple (A_1,...,A_p) of matrices of size n <r if the Z_i pairwise commute and each A_i sits in the upper left corner of a block decomposition of Z_i. 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=4n/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.