next up previous contents
Next: Ancestorless states for Up: The Garden of Previous: The use of

Systems of symbolic equations

In Conway's monograph[25] it is shown that the premise of Arden's lemma, that the symbolic equation X = aX + b can be solved by , is just as applicable to systems of equations if they are written in matrix notation. Thus if we define the following vectors and matrices

we can write one single matrix equation

whose solution would be

Of course, such a solution is not of much value unless there is an effective way to calculate the ``star'' of a matrix. Fortunately the matrix elements of the star are simple regular expressions of the elements of the matrix being starred, expressing in a concise form the results of the chain of substitutions that would otherwise be carried out explicitly each time a system of symbolic equations was to be solved. Indeed, the easiest way to establish the point is to go ahead and solve the equations: Given

we deduce in succession

Disentangling u and v from the final equations for P and Q yields a formula for

Although these results have been stated for a matrix, the fact that the matrix elements can be matrices themselves means that the results are valid in terms of submatrices. By repeated partitioning, in principle a system of any size can be reached. In practice, each partition multiplies the complexity of the symbolic expressions involved, quickly reaching unmanageable proportions. Alternative forms for these matrix elements can be derived using some of the identities satisfied by regular expressions, but the difficulty is a fundamental one---the formulas required are intrinsically complicated.

Harold V. McIntosh