*Ecological Archives*
E085-001-A2

**I. Miklós and J. Podani.
2004. Randomization of presence–absence matrices: comments and new algorithms.
***Ecology* 85:86–92.

Appendix B.Sum-of-squares
reduction never falls into an infinite cycle
In this appendix, we show that the
sum-of-squares reduction never falls into an infinite cycle, namely, if a matrix
has row and column totals identical to the row and column totals of a 0-1 matrix,
then it can be converted into a 0-1 matrix with quasi-swaps.

Notation: A quasi-swap replacing
the submatrix _{} by _{} is
denoted by (*ij*)(*kl*).

**Theorem** Let *M* = {*m*_{i,j}}
be a nonnegative integer matrix, with row totals **a**_{0 }= (_{})
and column totals

**b**_{0} = (_{}).
If a 0-1 matrix exists with the same row and column totals, then *M* can
be transformed into a 0-1 matrix using quasi-swaps.

**Proof** Let the column totals
be ordered decreasing.We prove that if column *r* has the smallest column
total *a*_{r}, then quasi swaps can transform *M* into *M*'
in which *r* has 1’s in the first *a*_{r} columns. It is enough
for the proof, according to the Havel-Hakimi theorem (Havel 1955,
Hakimi 1962).

First we prove that entities greater
than 1 can be eliminated from row *r* with quasi-swaps, and then we prove
that *M*' mentioned above can be reached with quasi-swaps, too. Assume
that for some column *c*, *m*_{r,c} > 1. Let
*C*_{1} = { *c*' | *m*_{rc’} >0
}, *R*_{1} = { *r*' | *m*_{r'c} > 0},
*R*_{2} = {*r'*|*a*_{r'} > 0}\*R*_{1},
*C*_{2} = {*c*'|*b*_{c'} > 0}\*C*_{1}.
Note that |*C*_{2}| > 0 and |*R*_{2}| > 0
since a 0-1 matrix exists with the same row and column totals. If there are
*c*_{2} *C*_{2}
and *r*_{2} *R*_{2}
with _{}>0,
then (*rc*)(*r*_{2}*c*_{2}) is a quasi-swap
resulting smaller *m*_{r,c}. If "*c*_{2}*C*_{2}
and "*r*_{2} *R*_{2}
_{} = 0,
then *c*_{1}
*C*_{1} and *r*_{2} *R*_{2}
exist such that _{} > _{}
since _{} ³*a*_{r}.
Hence (*r*_{2}*c*_{1})(*rc*) is an allowed swap
resulting in the sum of squared entities decreasing. Since the sum of squared
entities cannot be smaller than the sum of the entities, in a finite number
of steps we can eliminate all the entities greater than 1 from column *c*.

Now *r* has only 0’s and 1’s
and we are going to prove the existence of *M*'. Let *u* = min{*u*'|
*m*_{r,u'} = 0, *m*_{r,u' + 1} > 0}.
There is a *r*' for which *m*_{r',u'} > *m*_{r',u'}_{ + 1}
_{} £_{}
. Therefore (*ru' + 1*)(*r'u'*) is a quasi-swap. By induction
on *u* we can construct the desired M'.

Literature cited

Hakimi, S. 1962. On the realizability
of a set of integers as degrees of the vertices of a graph. SIAM Journal of
Applied Mathematics **10**:496–506.

Havel, V. 1955. A remark on the
existence of finite graphs. [In Czech.] Casopis pro Pestováni Matematiky **80:**477–480.

[Back to E085-001]