Re: Question on permutation matrix

In article <gerry-0C01DD.08580324102006@xxxxxxxxxxxxxxxxxx>,
Gerry Myerson <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
In article <1161627521.753819.203470@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
mittra@xxxxxxxx wrote:

I have a rather easy question for all you gurus out there. I write the
definition below for elaborating my question.

Def: A permutation matrix is defined as a p x p binary square matrix
such that any column or row of the matrix contains only one 1 and rests
are 0s.

Question: Can this general definition be expressed in no more than p
equations (or inequations)? If yes, how? If not, can you show the proof
that it can not be?

Note that, I am not defining a particular permutation matrix, just a
generic one.

At first glance, it seems unlikely. Say p = 3. There's a 9-dimensional
space of 3 x 3 matrices, and you want 3 equations to cut that space
down to 6 points.

But perhaps we're allowed to assume that we're living in the space
of 0-1 matrices. Maybe this works:

For i from 1 to p, the sum of the squares of the entries in row i
and in column i is 2.

E.g., for

a b c
d e f
g h i

we have a^2 + b^2 + c^2 + a^2 + d^2 + g^2 = 2,
d^2 + e^2 + f^2 + b^2 + e^2 + h^2 = 2,
c^2 + f^2 + i^2 + g^2 + h^2 + i^2 = 2.

If these are 0-1 matrices, why bother squaring?

No, that doesn't do it: try

[ 0 0 0 ]
[ 1 0 1 ]
[ 1 0 0 ]

But any finite set of equations over the integers (or reals) can be
expressed with one (nonlinear) equation: try

(a+b+c-1)^2 + (d+e+f-1)^2 + (g+h+i-1)^2 + (a+d+g-1)^2 + (b+e+h-1)^2
+ (c+f+i-1)^2 = 0

Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

.

Relevant Pages

  • Re: Question on permutation matrix
    ... definition below for elaborating my question. ... Def: A permutation matrix is defined as a p x p binary square matrix ...
    (sci.math)
  • Question on permutation matrix
    ... I have a rather easy question for all you gurus out there. ... definition below for elaborating my question. ... Def: A permutation matrix is defined as a p x p binary square matrix ...
    (sci.math)