# Termination conditions for matrix Lie alebra basis generation via "P. Hall algorithm"

Suppose $g_1,...,g_n\in\mathbb{M}_{d\times d}(\mathbb{C})$ are matrices and we are interested in finding the smallest matrix Lie algebra containing them, that is, the matrix Lie algebra generated by $g_1,...,g_n$. Specifically, we are interested in obtaining a vector space basis for this algebra. We are assuming the Lie operation is commutation.

Typically, one picks a linearly independent subset of $g_1,...,g_n$ (with the same linear span) and starts taking commutations. Commutations that are linearly independent to the previous elements are appended to this list until a basis is formed.

To avoid doing more work than necessary, since the Jacobi identity will cause checking some commutations to be redundant, one follows a strategy in the checked commutations. The strategy I am interested in are so called Philip Hall bases. See here for a quick reference.

My question is about stopping conditions. The trivial stopping condition is when you have enough elements to span $\mathfrak{gl}_d(\mathbb{C})$. The more interesting stopping condition occurs when the Lie algebra being generated is a proper subalgebra of $\mathfrak{gl}_d(\mathbb{C})$. I have heard rumours that if all P. Hall basis elements of a given depth $m\in\mathbb{N}$ are linearly dependent on P. Hall basis elements from smaller depths $m'<m$, then all P. Hall basis elements with depth $m'>m$ will also be linearly dependant on the elements with depth less than $m$.

Is this true?

Yes. The point of a P. Hall family is just an irredundant way to specify, e.g., a basis of the free Lie algebra on a generating set, avoiding redundancies due to the anticommutativity and Jacobi identity of the Lie bracket. The depth simply specifies how far down the lower central series of the free Lie algebra a bracket is. So if all elements of depth $m$ are linearly dependent on elements of depth $m' < m$, then a basis for the (finite-dimensional) Lie algebra is already given by the elements of depth $m-1$.