next up previous contents
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.

  equation1317

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 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 tex2html_wrap_inline5170 and tex2html_wrap_inline5172 , the equation tex2html_wrap_inline5174 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 tex2html_wrap_inline5184 , tex2html_wrap_inline5186 and tex2html_wrap_inline5174 . Moreover, if z exists, then tex2html_wrap_inline5170 .

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 tex2html_wrap_inline5184 , tex2html_wrap_inline5186 , it is necessarygif to show that the equation tex2html_wrap_inline5174 follows from the equations in the spreadsheet which do not involve either z or tex2html_wrap_inline5210 . One can either show this by hand or run NCProcess1 on the equations in the above spreadsheet which do not involve either z or tex2html_wrap_inline5210 together withgif the equation tex2html_wrap_inline5174 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 tex2html_wrap_inline5184 and tex2html_wrap_inline5186 .

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

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 tex2html_wrap_inline5288 is invertible, but still assume that d is invertible (and so, of course, assume that tex2html_wrap_inline5292 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 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 ( tex2html_wrap_inline5322 ) shows that
tex2html_wrap_inline5324 . 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 up previous contents
Next: Strategies and motivated unknowns Up: Examples: Matrix Completion Problems Previous: The partially prescribed

Helton
Wed Jul 3 10:27:42 PDT 1996