\documentclass[12pt]{article}
\usepackage{amsfonts}
\tolerance=10000
\renewcommand{\thefootnote}{*}
\renewcommand{\theequation}{\thesection.\arabic{equation}}
\newtheorem{thm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{prob}{Problem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\def\eqref#1{(\ref{#1})}
\def\qed{~\vrule height8pt width 5pt depth -1pt\medskip}


\begin{document}
%\noindent Image 26  2001

\centerline{{\bf Commutativity of EP Matrices}}

\bigskip

\noindent 
A  solution to Problem 26 - 4  
in Image April 2001 volume 26; 

\noindent
Proposed by Yongge Tian ytian@mast.Queensu.CA, 
\quad 
 Queens University, Kingston Ontario, Canada

\medskip

\centerline{Solution by J. Bell, J. William Helton, Anthony Shaheen}
\centerline{Math Dept UCSD, La Jolla, CAL  92093}
\centerline{Email: jbell@math.ucsd.edu, helton@ucsd.edu, ashaheen@math.ucsd.edu}

\begin{defn} A matrix $M\in M_n({\mathbb C})$ is said to be
EP if $M$ has the same column space as $M^*$.  Equivalently, $M$ is
EP if $M^{*}=MG$ for some invertible matrix $G$.
\end{defn}
A slight modification of the original Problem 26-4 is
\begin{thm} Let $A$ and $B$ be matrices in $M_n(\mathbb{C})$.
\vskip 1mm
a. If $A$ and $B$ commute, then
$A$ is EP only if $A^{\dagger}B-BA^{\dagger}=0$.
\vskip 1mm
b. If $A$ and $B$ are EP, then $A$ and $B$ commute if and only if 
$A^{\dagger}$ and $B^{\dagger}$ commute.
\end{thm}

\noindent
\emph{Solution.}\vskip 1mm
The goal is to give a proof based upon fairly automatic use of computer
algebra.  We use \emph{NCGB} package of \emph{NCAlgebra}.  Available
from \emph{www.math.ucsd.edu/$\sim$ncalg}.\vskip 1mm
(a) Problem  26-4 asked whether, under the condition that $A$ and
$B$ commute, $A$ is EP \emph{if and only if} $A^{\dagger}B-BA^{\dagger}$.
Observe that only one implication can  always be 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 $A^{\dagger}$ and $B$ commute using a noncommutative (NC) Gr\"obner basis 
algorithm.  
Such algorithms in the commutative case are the main tool for 
solving collections of polynomial equations or at least
for reducing them to a `` nice " form.
For noncommutative polynomials GB's are very experimental.
Recall that the input to a Gr\"obner basis algorithm has two parts.
The first part 
is a list
of polynomials, denoted by $\cal{S}$, which
in our solution of this problem is: 
\begin{enumerate}
\item{The polynomials } 
\begin{equation}
\Big\{ \big( AA^{\dagger}\big)^{*} - AA^{\dagger}, \big(
A^{\dagger}A\big)^{*} - A^{\dagger}A, AA^{\dagger}A-A,A^{\dagger}AA^{\dagger}-
A^{\dagger}\Big\} 
\label{eq: pseudo}
\end{equation} 
which when set to zero define the pseudo-inverse of $A$.
\item{The polynomial}
\begin{equation}
\Big\{ AB - BA \Big\}.
\end{equation}
\item{
The fact that $A$ is EP  gives
$$\Big\{ AG-A^{*}, GG^{-1}-1,G^{-1}G-1\Big\}.$$
}
\item{ One way
  to show that $A^{\dagger}$ and $B$
commute  
is to create an additional variable, $Q$,
and 
we adjoin
$Q-A^{\dagger}B+BA^{\dagger}$,
since we achieve our goal if $Q$ is 0.
}
\item{We adjoin the adjoints of the 
polynomials above. (NCAlgebra has 
a convenient command that accomplishes this.)
}
\end{enumerate}
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:
\begin{equation}
%\mathcal{O} \ = \ 
%\Big\{
(A^{\dagger})<(A^{\dagger})^{*}<A<A^{*}<B<B^{*}<G<G^{-1}<G^{*}<(G^{*})^{-1}<
Q<Q^{*}.
%\Big\}.
\label{eq: order}
\end{equation}
Recall that in a Gr\"obner 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 
{\tt NCProcess}, with options set so that it makes and sorts an NC Gr\"obner
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. 



  
% This result has the following interesting consequence.
% \begin{cor} If $A$ is EP, then $A$ and $A^{\dagger}$ commute.
% \label{cor: 1}
% \end{cor}
%

(b)   
Suppose $A$ and $B$ commute.  
Again we use the Gr\"obner basis package applied to the starting relations:
\begin{enumerate}
\item{The hypothesis that both $A$ and $B$ are EP is equivalent to the 
existence of $G$ and $H$ satisfying
$$\Big\{ AG-A^*, GG^{-1}-1,G^{-1}G-1, BH-B^*,HH^{-1}-1,H^{-1}H-1\Big\}.$$
}
\item{
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
$$\Big\{ AB^{\dagger}-B^{\dagger}A, BA^{\dagger}-A^{\dagger}B, AA^{\dagger}-
A^{\dagger}A, BB^{\dagger}-B^{\dagger}B\Big\}.$$
}
\item{The polynomial}
\begin{equation}
\Big\{ AB - BA \Big\}.
\end{equation}
\item{
We adjoin the defining polynomials for the pseudo inverse of $A$ given
in equation (\ref{eq: pseudo}) and the corresponding polynomials for $B$.
}
\item{Once again, our objective is achieved if the additional
variable $Q$ satisfying the equation
$$Q-A^{\dagger}B^{\dagger}+B^{\dagger}A^{\dagger}$$ is zero.
}
\item{ We adjoin the adjoints of the above equations.}
\end{enumerate}
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 $A^{\dagger}$ and $B^{\dagger}$ 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 
$$\Big\{ AB-BA \Big\}$$ by 
%$$\Big\{ AB-BA, 1B^{*}A^{*}-A^{*}B^*\Big\}$$ by 
$$\Big\{ A^{\dagger}B^{\dagger}-B^{\dagger}A^{\dagger}
\Big\}$$
%$$\Big\{ A^{\dagger}B^{\dagger}-B^{\dagger}A^{\dagger},
%(B^{\dagger})^*(A^{\dagger})^*-(A^{\dagger})^*(B^{\dagger})^*\Big\}$$
and redefine
$Q$ by adjoining the polynomial $Q-AB +BA$
instead of $Q-A^{\dagger}B^{\dagger}+B^{\dagger}A^{\dagger}$;
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$. \qed

This solves problem 
 Problem 26 - 4  
by fairly automatic use of NCAlgebra's 
noncommutative Gr\"obner basis package
and suggests a problem of our own:

\begin{quote}
{\bf 
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 in an automatic fashion  to computer algebra?}
\end{quote}

\vskip 3mm
\noindent Submitted to:\\
styan@math.mcgill.ca\\
\vskip 2mm
\noindent George Styan,\\
Department of Mathematics and Statistics,
McGill University,\\
Burnside Hall Room 1240,\\
805 Sherbrooke W. Montreal. Qc. H3A 2K6 

\end{document}