15.4.3.3 Philip Hall basis of a Lie algebra

Determining the basis of a Lie algebra may be a long and tedious process. The combinations of Lie brackets in Example 15.17 were given; however, it is not known in advance which ones will produce independent vector fields. Numerous Lie brackets may be needed, including some that are nested, such as $[[h_1,h_2],h_3]$. The maximum depth of nested Lie bracket operations is not known a priori. Therefore, a systematic search must be performed (this can in fact be modeled as a discrete planning problem) by starting with $h_1$, $\ldots$, $h_m$ and iteratively generating new, independent vector fields using Lie brackets.

One popular approach is to generate the Philip Hall basis (or P. Hall basis) of the Lie algebra ${\cal L}({\triangle})$. The construction of the basis essentially follows breadth-first search, in which the search depth is defined to be the number of nested levels of bracket operations. The order (or depth) $d$ of a Lie product is defined recursively as follows. For the base case, let $d(h_i) = 1$ for any of the system vector fields. For any Lie product $[\phi_1,\phi_2]$, let

$$d([\phi_1,\phi_2]) = d(\phi_1) + d(\phi_2) .$$ (15.108)

Thus, the order is just the nesting depth (plus one) of the Lie bracket operations. For example, $d([h_1,h_2]) = 2$ and $d([h_1,[h_2,h_3]]) = 3$.

In addition to standard breadth-first search, pruning should be automatically performed to ensure that the skew symmetry and Jacobi identities are always utilized to eliminate redundancy. A P. Hall basis is a sequence, ${\cal PH}= (\phi_1$, $\phi_2$, $\ldots)$, of Lie products for which:

1. The system vector fields $h_i$ are the first $m$ elements of ${\cal PH}$.
2. If $d(\phi_i) < d(\phi_j)$, then $i < j$.
3. Each $[\phi_i,\phi_j] \in {\cal PH}$ if and only if: a) $\phi_i,\phi_j \in {\cal PH}$ and $i < j$, and b) either $\phi_j = h_i$ for some $i$ or $\phi_j = [\phi_l,\phi_r]$ for some $\phi_l,\phi_r \in {\cal PH}$ such that $l \leq i$.

It is shown in many algebra books (e.g., [861]) that this procedure results in a basis for the Lie algebra ${\cal L}({\triangle})$. Various algorithms for computing the basis are evaluated in [299].

Example 15..18 (P. Hall Basis Up to Depth Three)   The P. Hall basis sorts the Lie products into the following sequence, which is obtained up to depth $d = 3$:

$h_1$,	$h_2$,	$h_3$,
$[h_1,h_2]$,	$[h_2,h_3]$,	$[h_1,h_3]$,
$[h_1,[h_1,h_2]]$,	$[h_1,[h_1,h_3]]$,	$[h_2,[h_1,h_2]]$,	$[h_2,[h_1,h_3]]$,
$[h_2,[h_2,h_3]]$,	$[h_3,[h_1,h_2]]$,	$[h_3,[h_1,h_3]]$,	$[h_3,[h_2,h_3]]$ .

So far, the only Lie product eliminated by the Jacobi identity is $[h_1,[h_2,h_3]]$ because

$$[h_1,[h_2,h_3]] = [h_2,[h_1,h_3]] - [h_3,[h_1,h_2]] .$$ (15.109)

Note that all of the Lie products given here may not be linearly independent vector fields. For a particular system, linear independence tests should be performed to delete any linearly dependent vector fields from the basis. $\blacksquare$

When does the sequence ${\cal PH}$ terminate? Recall that $\dim({\cal L}({\triangle}))$ can be no greater than $n$, because ${\cal L}_x({\triangle}) \subseteq T_x(X)$. In other words, at every state $x \in X$, the number of possible independent velocity vectors is no more than the dimension of the tangent space at $x$. Therefore, ${\cal PH}$ can be terminated once $n$ independent vector fields are obtained because there is no possibility of finding more. For some systems, there may be a depth $k$ after which all Lie brackets are zero. Such systems are called nilpotent of order $k$. This occurs, for example, if all components of all vector fields are polynomials. If the system is not nilpotent, then achieving termination may be difficult. It may be the case that $\dim({\cal L}({\triangle}))$ is strictly less than $n$, but this is usually not known in advance. It is difficult to determine whether more Lie brackets are needed to increase the dimension or the limit has already been reached.