Riepilogo Tecnico: Inversione dell'Operatore Composto Moltiplicativo

Enunciato del Problema

Il lavoro affronta il problema inverso dell'operatore composto moltiplicativo di ordine $k$. Data una matrice $M \in \mathbb{R}^{\binom{n}{k} \times \binom{m}{k}}$, l'obiettivo è determinare se esiste una matrice $A \in \mathbb{R}^{n \times m}$ tale che $M = C_k(A)$, dove $C_k(A)$ denota il composto moltiplicativo di ordine $k$ di $A$. Se una tale matrice esiste (ovvero, se $M$ è "decomponibile in composto"), il lavoro mira a caratterizzare l'insieme di tutte le tali pre-immagini $A$ e a fornire un algoritmo costruttivo per recuperarle.

Gli autori osservano che, sebbene le matrici composte siano ampiamente studiate nell'algebra lineare, nei sistemi dinamici e nella teoria del controllo (citando lavori di Schwarz, Li, Muldowney e altri), il specifico problema inverso di recuperare $A$ da $C_k(A)$ non era stato precedentemente considerato.

Metodologia e Algoritmo

La soluzione proposta si basa sulla Decomposizione ai Valori Singolari (SVD) e sulle proprietà dell'algebra esterna. La metodologia procede assumendo che i valori singolari non nulli della matrice di input $M$ siano distinti (condizione che può essere garantita tramite una fase di pre-elaborazione generica che coinvolge una trasformazione invertibile).

L'algoritmo centrale scompone il processo di recupero in quattro fasi principali:

1. Decomposizione a Cuneo (Recupero dei Vettori Singolari):
   L'algoritmo tratta le colonne delle matrici dei vettori singolari sinistro ($L$) e destro ($R$) di $M$ come vettori decomponibili nello spazio esterno di ordine $k$. Utilizzando la proprietà secondo cui un vettore decomponibile $z = u_1 \wedge \dots \wedge u_k$ definisce univocamente il sottospazio $\text{span}\{u_1, \dots, u_k\}$, gli autori costruiscono "matrici a cuneo" $M_z$ i cui nuclei corrispondono a tali sottospazi. Calcolando i nuclei di queste matrici e trovando le loro intersezioni a due a due di dimensione uno, l'algoritmo recupera i singoli vettori singolari di $A$ (a meno di un segno). Questa fase è formalizzata nel Teorema 2 e nell'Algoritmo 1.

2. Ordinamento dei Valori Singolari:
   Poiché i valori singolari di $M$ (gli elementi diagonali di $S$ in $M=LSR^\top$) non sono necessariamente ordinati nello stesso modo dei valori singolari composti di $A$, l'algoritmo utilizza i vettori singolari recuperati $\hat{V}$ per calcolare $C_k(\hat{\Sigma})$. Ciò permette di riordinare gli elementi diagonali di $S$ in modo da corrispondere all'ordine lessicografico dei valori singolari composti.

3. Ripristino della Coerenza dei Segni:
   La fase di decomposizione a cuneo recupera i vettori singolari a meno di un segno arbitrario. Poiché i segni dei vettori singolari sinistro e destro devono essere coerenti per ricostruire $A$, viene impiegato l'Algoritmo 2. Sfrutta la proprietà moltiplicativa dell'operatore composto per allineare i segni dei vettori singolari sinistro e destro recuperati, garantendo che $C_k(\hat{V})$ e $C_k(\hat{W})$ corrispondano ai segni di $L$ e $R$ rispettivamente.

4. Recupero dei Valori Singolari:
   Una volta stabiliti i vettori singolari e i valori singolari composti ordinati, i valori singolari originali di $A$ vengono recuperati risolvendo un sistema lineare. La relazione tra i valori singolari di $A$ ($\sigma_i$) e gli elementi diagonali di $C_k(\Sigma)$ è moltiplicativa ($\prod \sigma_i$). Prendendo i logaritmi, questa relazione si trasforma in un sistema lineare $y = Lx$, dove $x = \log(\sigma)$, che viene risolto in modo univoco come mostrato nel Lemma 8.

Contributi e Risultati Chiave

1. Caratterizzazione dell'Unicità

Il lavoro fornisce una caratterizzazione completa dell'insieme delle pre-immagini basata sul rango di $M$:

• Caso $\text{rango}(M) \le 1$: Se $k > \text{rango}(A)$, allora $C_k(A) = 0$. Se $k = \text{rango}(A)$ e $\text{rango}(M)=1$, esistono infiniti matrici $A$ tali che $C_k(A) = M$. Nello specifico, se $A = UV^\top$ è una fattorizzazione rivelatrice del rango, qualsiasi matrice $B = UTV^\top$ con $\det(T)=1$ produce lo stesso composto.
• Caso $\text{rango}(M) > 1$: Se $k < \text{rango}(A)$, la pre-immagine è unica a meno di un segno globale. Cioè, se $C_k(A) = C_k(B)$, allora $A = B$ (se $k$ è dispari) o $A = \pm B$ (se $k$ è pari).

2. Algoritmo Costruttivo e Complessità

Gli autori presentano un algoritmo a tempo polinomiale per recuperare la matrice $A$. La complessità temporale è analizzata nel Teorema 1:

• Per $k < \lceil \text{rango}(A)/2 \rceil$, la complessità è $O(\max_{p \in \{m,n\}} [\binom{p}{k}^3 + \binom{p}{k}^2 \binom{r}{k}])$.
• Per $k$ più grandi, la complessità include un ulteriore fattore logaritmico relativo all'intersezione iterativa dei sottospazi.
• L'algoritmo è implementato in MATLAB ed è disponibile pubblicamente.

3. Casi Particolari

Il lavoro nota una soluzione in forma chiusa per il caso specifico in cui $k = n-1$ e $M$ è invertibile, derivata utilizzando le proprietà della matrice aggiunta e il teorema di Sylvester-Franke (Corollario 1). Tuttavia, per $n, m, k$ generali, l'algoritmo costruttivo rappresenta il contributo principale.

Significato e Affermazioni

Il lavoro afferma di risolvere un problema inverso fondamentale nell'algebra lineare che non era stato precedentemente affrontato. La sua rilevanza risiede in:

• Completezza Teorica: Stabilisce condizioni necessarie e sufficienti per l'esistenza di un composto inverso e caratterizza pienamente l'insieme delle soluzioni (unica vs infinita).
• Fattibilità Computazionale: Fornisce un algoritmo deterministico a tempo polinomiale per recuperare la matrice, superando la mera esistenza teorica per passare al calcolo pratico.
• Fondamento per Applicazioni: Gli autori collocano questo lavoro come prerequisito per applicazioni nei sistemi dinamici e nella teoria del controllo. Nello specifico, osservano che determinare se un sistema può essere trasformato in un sistema "$k$-positivo" (dove il $k$-esimo composto ha segni uniformi) richiede la capacità di realizzare una data matrice come un composto. Questa capacità inversa permette ai ricercatori di verificare se esiste una tale trasformazione di coordinate e di costruirne una.

Gli autori mantengono un tono modesto riguardo al lavoro futuro, affermando esplicitamente che la questione di se una data matrice arbitraria sia decomponibile in composto rimane un problema aperto, e che trovare le migliori approssimazioni per matrici non decomponibili è una direzione per la ricerca futura.