Cheap and Secure Web Hosting Provider : See Now

# Arden's rule expressed as matrix algebra

, ,
Problem Detail:

The following theorem is (in the context of languages) known as Arden's Lemma: Given a linear system $X = B+AX$ and the matrix A is quasiregular, then we have a solution which is unique and which preserves rationality. In the next lemma we show the converse: For every rational series we can find a linear system such that the first component of its solution vector is exactly the given series. With these two results we have already done most of the work for proving the Theorem of Schutzenberger, which teaches us that the families of rational and recognizable series coincide.

# Theorem 2.2.1

Let $B \in \mathbb{K}\langle\langle\Sigma^*\rangle\rangle^{n,1}$ and $A \in \mathbb{K}\langle\langle\Sigma^*\rangle\rangle^{n,n}$ a quasiregular matrix. The linear system

$$X = B + AX$$

has the unique solution $X = A^∗B$. Moreover, if $A$ and $B$ are $\mathbb{K}-rational$ then the solution $X$ is $\mathbb{K}-rational$.

## Proof:

First we show that $X = A^∗B$ is a solution:

$$B + AX = B + AA^∗ B = (I + AA^∗)B = A^∗B = X.$$

My question is as follows: what does asterisk mean in this context (when it is used with matrices)? I know what Arden's Lemma is, but I don't understand the proof given here.

To credit the author of this paper: Regular Languages And Their Generating Functions: The Inverse Problem by Christoph Koutschan.

#### Answered By : Yuval Filmus

The notation is probably defined in the paper or in some standard reference, but one can guess that $$A^* = (I - A)^{-1}.$$ This definition satisfies the identity $A^* = I+AA^*$, since $$I+AA^* = I-((I-A)-I)A^* = I-(I-A)A^*+A^* = I-I+A^* = A^*.$$ Presumably a quasiregular matrix $A$ is one for which $I-A$ is invertible, perhaps with some additional assumptions.