**Lemma 4.2 [Y]***
Let a be an m × m matrix, c be an n × m matrix and d
be an m × n matrix z such that
*

*
is a contraction if and only if
*

Since we can not handle inequalities, we analyze the case where
the unknown matrix *z* must be chosen to make
the matrix of (§) unitary.

Per our usual advice, when just starting a problem, we take
most matrices to be invertible. Since only *a* and
*d* are square, we assume that *a* and *d* are invertible.

If *a* and *d* are invertible, then
the matrix of (§) is unitary if
and only if the following polynomials are zero.

When we run NCProcess1 on these equations, we obtain the following spreadsheet:

THE ORDER IS NOW THE FOLLOWING:

*a* <
*a*
<
*a*
<
*a*
< *c* <
*c*
< *d* <
*d*
<
*d*
<
*d*
« *z* «
*z*

YOUR SESSION HAS DIGESTED | ||
---|---|---|

THE FOLLOWING RELATIONS | ||

{

The corresponding rules are the following:

*z*
-*a*
*c*
*d*

*z*
-*d*
*c*
*a*

The expressions with unknown variables {}

and knowns {

*a*
*a*
1

*a*
*a*
1

*a*
*a*
1

*a*
*a*
1

*d*
*d*
1

*d*
*d*
1

*d*
*d*
1

*d*
*d*
1

*d*
*d*
1 -
*c*
*c*

*c*
*c*
1 -
*a*
*a*

| ||
---|---|---|

USER CREATIONS APPEAR BELOW |
| |

| ||||
---|---|---|---|---|

SOME RELATIONS WHICH APPEAR BELOW |
| |||

| MAY BE UNDIGESTED |
| ||

{}

Since the above spreadsheet
contains the equations and ,
the equation follows from
the above spreadsheet.
The above spreadsheet and the observation just made
shows that, if *a*, *c*
and *d* are invertible, then
there exists a matrix *z* such that
the matrix of (§) is unitary if and only if
, and
.
Moreover, if *z* exists, then .

To show that
under the above invertibility assumptions,
there exists an *m × n*
matrix *z* such that
the matrix of (§) is unitary if and only if
, , it is
necessary
to show that the equation
follows
from the equations in the spreadsheet which do
not involve either *z* or . One can either
show this by hand or run NCProcess1 on the equations
in the above spreadsheet which do not involve
either *z* or together with
the equation
and see that
this equation is redundant.
In summary,
if *a*, *c* and *d* are invertible,
there exists a matrix *z* such that
the matrix of (§) is unitary if and only if
and .

Since we assumed that *a* and *d* were invertible, the above
calculation has a ``back of the envelope''
flavor.
Now that our ``back of the envelope'' calculation assuming
invertibility
was successful, it is easy to remove the invertibility assumptions.
If we do not assume that *a* and *d* are invertible, NCProcess1
produces the spreadsheet:

THE ORDER IS NOW THE FOLLOWING:

*a* <
*a*
< *c* <
*c*
< *d* <
*d*
«
*z*
«
*z*

YOUR SESSION HAS DIGESTED | ||
---|---|---|

THE FOLLOWING RELATIONS | ||

and knowns {

*d*
*d*
1 - *c*
*c*

*c*
*c*
1 -
*a*
*a*

| ||
---|---|---|

USER CREATIONS APPEAR BELOW |
| |

| ||||
---|---|---|---|---|

SOME RELATIONS WHICH APPEAR BELOW |
| |||

| MAY BE UNDIGESTED |
| ||

{

The expressions with unknown variables {

and knowns {

*z*
*d*
-*a*
*c*

*a*
*z*
-*c*
*d*

The expressions with unknown variables {

and knowns {

*d*
*z*
-*c*
*a*

*z*
*a*
-*d*
*c*

The expressions with unknown variables {

and knowns {

*z*
*z*
1 -
*a*
*a*

*z*
*z*
1 -
*d*
*d*

One could use these equations to push through to the unitary case of Parrot's Lemma. However, since the theorem is well known, there is not much point in publishing this derivation.

Notice from the spreadsheet above that if *d* is invertible,
then one can solve for *z*. So far, we only have a result
for the case that both *a* and *d* are invertible. Let
us consider the case when only *d* is invertible and
see what happens.
If we do not assume that *a* or is invertible, but still
assume that *d* is invertible (and so, of course, assume that
is invertible), then we obtain the following
spreadsheet:

THE ORDER IS NOW THE FOLLOWING:

*a* <
*a*
< *c* <
*c*
< *d* <
*d*
<
*d*
<
*d*
« *z* «
*z*

YOUR SESSION HAS DIGESTED | ||
---|---|---|

THE FOLLOWING RELATIONS | ||

{

The corresponding rules are the following:

*z*
-*a*
*c*
*d*

*z*
-*d*
*c*
*a*

The expressions with unknown variables {}

and knowns {

*d*
*d*
1

*d*
*d*
1

*d*
*d*
1

*d*
*d*
1

*d*
*d*
1 -
*c*
*c*

*c*
*c*
1 -
*a*
*a*

*a*
*c*
*d*
*d*
*c*
*a*
1 -
*a*
*a*

| ||
---|---|---|

USER CREATIONS APPEAR BELOW |
| |

| ||||
---|---|---|---|---|

SOME RELATIONS WHICH APPEAR BELOW |
| |||

| MAY BE UNDIGESTED |
| ||

{}

Notice that the last expression in
spreadsheet ( )
shows that

.
Therefore, the matrix *a* is onto. Since *a* is a square matrix,
*a* is invertible.
Thus, by using the spreadsheet and
the special properties of matrices (rather than elements
of an arbitrary abstract algebra) we have discovered that
if *d* is invertible, then *a* is invertible.
At this point in the session we would add the fact
that
*a* is invertible, run NCProcess1 and one would obtain the
first spreadsheet of
§.

Wed Jul 3 10:27:42 PDT 1996