Next: Strategies and motivated unknowns Up: Examples: Matrix Completion Problems Previous: The partially prescribed

Unitary case of Parrot's Lemma

We begin by stating Parrot's Lemma.

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

THE FOLLOWING RELATIONS

THE FOLLOWING VARIABLES HAVE BEEN SOLVED FOR:
{z, z}
The corresponding rules are the following:

z -a c d

z -d c a

The expressions with unknown variables {}
and knowns {a, c, d, a, d, a, d, a, c, d}

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

THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR:
{}

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

THE FOLLOWING RELATIONS

The expressions with unknown variables {}
and knowns {a, c, d, a, c, d}

d d 1 - c c

c c 1 - a a

USER CREATIONS APPEAR BELOW

SOME RELATIONS WHICH APPEAR BELOW

MAY BE UNDIGESTED

THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR:
{z, z}
The expressions with unknown variables {z}
and knowns {a, d, a, c, d}

z d -a c

a z -c d

The expressions with unknown variables {z}
and knowns {a, c, d, a, d}

d z -c a

z a -d c

The expressions with unknown variables {z, z}
and knowns {a, d, a, d}

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

THE FOLLOWING RELATIONS

THE FOLLOWING VARIABLES HAVE BEEN SOLVED FOR:
{z, z}
The corresponding rules are the following:

z -a c d

z -d c a

The expressions with unknown variables {}
and knowns {a, c, d, d, d, a, c, d}

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

THE FOLLOWING VARIABLES HAVE NOT BEEN SOLVED FOR:
{}

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 §.

Next: Strategies and motivated unknowns Up: Examples: Matrix Completion Problems Previous: The partially prescribed

Helton
Wed Jul 3 10:27:42 PDT 1996