Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-168 | 9th December 2011 18:50

Lie algebra conjugacy



We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set $\mathcal{L}$ of matrices such that $A,B \in \mathcal{L}$ implies$AB - BA \in \mathcal{L}$. Two matrix Lie algebras are conjugate if there is an invertible matrix $M$ such that $\mathcal{L}_{1} = M \mathcal{L}_{2} M^{-1}$.

We show that certain cases of Lie algebra conjugacy are equivalent to graph isomorphism. On the other hand, we give polynomial-time algorithms for other cases of Lie algebra conjugacy, which allow us to mostly derandomize a recent result of Kayal on affine equivalence of polynomials. Affine equivalence is related to many complexity problems such as factoring integers, graph isomorphism, matrix multiplication, and permanent versus determinant.

Specifically, we show:

Abelian Lie algebra conjugacy is as hard as graph isomorphism. A Lie algebra is abelian if all of its matrices commute pairwise.

Abelian diagonalizable Lie algebra conjugacy of $n \times n$ matrices can be solved in $poly(n)$ time when the Lie algebras have dimension $O(1)$. The dimension of a Lie algebra is the maximum number of linearly independent matrices it contains. A Lie algebra $\mathcal{L}$ is diagonalizable if there is a single matrix $M$ such that for every $A$ in $\mathcal{L}$, $MAM^{-1}$ is diagonal.

Semisimple Lie algebra conjugacy is equivalent to graph isomorphism. A Lie algebra is semisimple if it is a direct sum of simple Lie algebras.

Semisimple Lie algebra conjugacy of $n \times n$ matrices can be solved in polynomial time when the Lie algebras consist of only $O(\log n)$ simple direct summands.

Conjugacy of completely reducible Lie algebras---that is, a direct sum of an abelian diagonalizable and a semisimple Lie algebra---can be solved in polynomial time when the abelian part has dimension $O(1)$ and the semisimple part has $O(\log n)$ simple direct summands.

ISSN 1433-8092 | Imprint