Technical Summary: Inversion of the Multiplicative Matrix Compound Operator

Problem Statement

The paper addresses the inverse problem of the $k$-th multiplicative compound operator. Given a matrix $M \in \mathbb{R}^{\binom{n}{k} \times \binom{m}{k}}$, the objective is to determine if there exists a matrix $A \in \mathbb{R}^{n \times m}$ such that $M = C_k(A)$, where $C_k(A)$ denotes the $k$-th multiplicative compound of $A$. If such a matrix exists (i.e., $M$ is "compound-decomposable"), the paper seeks to characterize the set of all such pre-images $A$ and provide a constructive algorithm to recover them.

The authors note that while compound matrices are well-studied in linear algebra, dynamical systems, and control theory (citing works by Schwarz, Li, Muldowney, and others), the specific inverse problem of recovering $A$ from $C_k(A)$ had not been previously considered.

Methodology and Algorithm

The proposed solution relies on the Singular Value Decomposition (SVD) and the properties of exterior algebra. The methodology proceeds under the assumption that the non-zero singular values of the input matrix $M$ are distinct (a condition that can be ensured via a generic preprocessing step involving an invertible transformation).

The core algorithm decomposes the recovery process into four main steps:

1. Wedge-Decomposition (Singular Vector Recovery):
   The algorithm treats the columns of the left ($L$) and right ($R$) singular vector matrices of $M$ as decomposable vectors in the $k$-th exterior power. Using the property that a decomposable vector $z = u_1 \wedge \dots \wedge u_k$ uniquely defines the subspace $\text{span}\{u_1, \dots, u_k\}$, the authors construct "wedge matrices" $M_z$ whose kernels correspond to these subspaces. By computing the kernels of these matrices and finding their one-dimensional pairwise intersections, the algorithm recovers the individual singular vectors of $A$ (up to a sign). This step is formalized in Theorem 2 and Algorithm 1.

2. Ordering Singular Values:
   Since the singular values of $M$ (diagonal entries of $S$ in $M=LSR^\top$) are not necessarily ordered in the same way as the compound singular values of $A$, the algorithm uses the recovered singular vectors $\hat{V}$ to compute $C_k(\hat{\Sigma})$. This allows the reordering of the diagonal entries of $S$ to match the lexicographical order of the compound singular values.

3. Sign-Consistency Restoration:
   The wedge-decomposition step recovers singular vectors up to an arbitrary sign. Since the signs of the left and right singular vectors must be consistent to reconstruct $A$, Algorithm 2 is employed. It exploits the multiplicative property of the compound operator to align the signs of the recovered left and right singular vectors, ensuring that $C_k(\hat{V})$ and $C_k(\hat{W})$ match the signs of $L$ and $R$ respectively.

4. Singular Value Recovery:
   Once the singular vectors and the ordered compound singular values are established, the original singular values of $A$ are recovered by solving a linear system. The relationship between the singular values of $A$ ($\sigma_i$) and the diagonal entries of $C_k(\Sigma)$ is multiplicative ($\prod \sigma_i$). Taking logarithms transforms this into a linear system $y = Lx$, where $x = \log(\sigma)$, which is solved uniquely as shown in Lemma 8.

Key Contributions and Results

1. Characterization of Uniqueness

The paper provides a complete characterization of the pre-image set based on the rank of $M$:

• Case $\text{rank}(M) \le 1$: If $k > \text{rank}(A)$, then $C_k(A) = 0$. If $k = \text{rank}(A)$ and $\text{rank}(M)=1$, there exist infinitely many matrices $A$ such that $C_k(A) = M$. Specifically, if $A = UV^\top$ is a rank-revealing factorization, any matrix $B = UTV^\top$ with $\det(T)=1$ yields the same compound.
• Case $\text{rank}(M) > 1$: If $k < \text{rank}(A)$, the pre-image is unique up to an overall sign. That is, if $C_k(A) = C_k(B)$, then $A = B$ (if $k$ is odd) or $A = \pm B$ (if $k$ is even).

2. Constructive Algorithm and Complexity

The authors present a polynomial-time algorithm to recover the matrix $A$. The time complexity is analyzed in Theorem 1:

• For $k < \lceil \text{rank}(A)/2 \rceil$, the complexity is $O(\max_{p \in \{m,n\}} [\binom{p}{k}^3 + \binom{p}{k}^2 \binom{r}{k}])$.
• For larger $k$, the complexity involves an additional logarithmic factor related to the iterative intersection of subspaces.
• The algorithm is implemented in MATLAB and is available publicly.

3. Special Cases

The paper notes a closed-form solution for the specific case where $k = n-1$ and $M$ is invertible, derived using properties of the adjugate matrix and the Sylvester-Franke theorem (Corollary 1). However, for general $n, m, k$, the constructive algorithm is the primary contribution.

Significance and Claims

The paper claims to solve a fundamental inverse problem in linear algebra that had not been previously addressed. Its significance lies in:

• Theoretical Completeness: It establishes necessary and sufficient conditions for the existence of an inverse compound and fully characterizes the solution set (unique vs. infinite).
• Computational Feasibility: It provides a deterministic, polynomial-time algorithm to recover the matrix, moving beyond theoretical existence to practical computation.
• Foundation for Applications: The authors position this work as a prerequisite for applications in dynamical systems and control theory. Specifically, they note that determining whether a system can be transformed into a "k-positive" system (where the $k$-th compound has uniform signs) requires the ability to realize a given matrix as a compound. This inverse capability allows researchers to verify if such a coordinate transformation exists and to construct it.

The authors remain modest regarding future work, explicitly stating that the question of whether a given arbitrary matrix is compound-decomposable remains an open problem, and that finding best approximations for non-decomposable matrices is a direction for future research.