Commutativity of EP Matrices

A solution to Problem 26 - 4 in Image April 2001 volume 26; proposed by Yongge Tian ytian@mast.Queensu.CA
Queens University, Kingston Ontario, Canada

Solution by J. Bell, J. William Helton, Anthony Shaheen

Math Dept UCSD, La Jolla, CAL 92093

Email: jbell@math.ucsd.edu,helton@ucsd.edu,ashaheen@math.ucsd.edu


defn23

A slight modification of the original Problem 26-4 is

thm27

Solution.

The goal is to give a proof based upon fairly automatic use of computer algebra. We use NCGB package of NCAlgebra. Available from http://www.math.ucsd.edu/~ncalg.

(a) Problem 26-4 asked whether, under the condition that A and B commute, A is EP if and only if tex2html_wrap_inline190 . Observe that only one implication is always true, for if B is the identity matrix, then B commutes with both A and its pseudo-inverse regardless of whether A is EP or not.

In the other direction, if A and B commute and A is EP, then we show that tex2html_wrap_inline206 and B commute using a noncommutative (NC) Gröbner basis algorithm. Recall that the input to a Gröbner basis algorithm has two parts. The first part is a list of polynomials, denoted by tex2html_wrap_inline210 , which in our solution of this problem is:

  1. The polynomials

      equation45

    which when set to zero define the pseudo-inverse of A.

  2. The polynomial

    equation59

  3. The fact that A is EP gives

    displaymath216

  4. One way to show that tex2html_wrap_inline206 and B commute is to create an additional variable, Q, and we adjoin tex2html_wrap_inline224 , since we achieve our goal if Q is 0.
  5. We adjoin the adjoints of the polynomials above. (NCAlgebra has a convenient command that accomplishes this.)

The second part of the input is an order on monomials which typically is induced by an order on the variables in the problem. In our case the order is degree lexicographic order induced by the following order on variables:

  equation69

Recall that in a Gröbner basis algorithm variables which are high in the order tend to be eliminated before variables which are low in the order.

We use the command NCProcess, with options set so that it makes and sorts an NC Gröbner basis by running Mora's algorithm for four iterations and removes some redundant polynomials. This makes a long list of polynomial equations, one of which is Q=0. This shows that part (a) is true. The run took 49 minutes on a 1 GigaHertz Pentium III machine with one gigabyte of RAM.

(b) Suppose A and B commute. Again we use the Gröbner basis package applied to the starting relations:

  1. The hypothesis that both A and B are EP is equivalent to the existence of G and H satisfying

    displaymath242

  2. Applying part (a) to the pairs A and B which commute, B and A which commute, A and itself, and B and itself allows us to adjoin the relations

    displaymath256

  3. The polynomial

    equation59

  4. We adjoin the defining polynomials for the pseudo inverse of A given in equation (0.1) and the corresponding polynomials for B.
  5. Once again, our objective is achieved if the additional variable Q satisfying the equation

    displaymath264

    is zero.

  6. We adjoin the adjoints of the above equations.
We choose a degree lexicographic order with Q at the top. (We found, when Q is placed at the top of the order, the result to be insensitive to the rest of the order in 4 experiments.) We ran NCProcess with options set to 2 iterations and among the output was Q=0. It follows that tex2html_wrap_inline206 and tex2html_wrap_inline274 commute, thus establishing the ``if'' part of (b). These runs took less than a minute.

The converse is obtained similarly. In the input polynomials we merely replace

displaymath276

by

displaymath278

and redefine Q by adjoining the polynomial Q-AB +BA instead of tex2html_wrap_inline284 ; we do this since our goal is now to show that A and B commute. Again we choose a degree lexicographic order with Q at the top and find after 3 iterations and about 15 minutes that Q=0. Again we tried some variations on the orders and in each case found that Q=0.

This solves problem Problem 26 - 4 by fairly automatic use of NCAlgebra's noncommutative Gröbner basis package and suggests a problem of our own: Now that some noncommutative computer algebra is available, which of the purely algebraic problems ( with a modest number of variables and equations ) that have been posed over the past years in Image succumb to computer algebra?

Submitted to:
werner@united.econ.uni-bonn.de Hans Joachim Werner,
IMAGE Editor-in-Chief,
Institute for Econometrics and Operations Research, Econometrics Unit,
University of Bonn,
Adenauerallee 24-42m D-53113
Bonn, Germany


FILES:

This document (.tex) (.ps) (.pdf).

Here are the files for (a)'s run:

  1. The mathematica file.
  2. The output (.ps ) (.pdf) file.

Here are the files for (b)'s run:

Forwards direction:

  1. The mathematica file.
  2. The output (.ps) (.pdf) for run 1.
  3. The output (.ps) (.pdf) for run 2.
  4. The output (.ps) (.pdf) for run 3.
  5. The output (.ps) (.pdf) for run 4.

Backwards direction:

  1. The mathematica file
  2. The output (.ps) (.pdf) for run 1.
  3. The output (.ps) (.pdf) for run 2.
  4. The output (.ps) (.pdf) for run 3.
  5. The output (.ps) (.pdf) for run 4.
Note: The different runs in part (b) are just with different orderings.