help-octave
[Top][All Lists]

Re: uniq matrix odering

 From: Daniel Heiserer Subject: Re: uniq matrix odering Date: Thu, 30 Sep 1999 12:19:29 +0200

```address@hidden wrote:
>
> Daniel,
>
> This is an interesting question, but I am afraid I don't
> understand it clearly enough.
>
> Suppose you have the matrix
>
>      1 1 0 0
>      0 1 1 0
>      0 0 1 1
>
> and you can permute independently the rows and the columns.
> Now, what would you like to get to know?

Hmm. I think I have to explain it once more....

I allow infinite permutations (exchanges of rows):
a_ij ==> a_kj && a_kj ==> a_ij  for all j's (using an intermediate
storage of course)

octave>> a=a([perturb(1:size(a,1))],:);
where "perturb" should be function which just reorders the elements of a
vector (no matter how).
I also allow infinite permutaions of columns:
a_ij ==> a_ik && a_ik ==> a_ij  ""
octave>> a=a(:,[perturb(1:size(a,2))]);

If I see it right the number of allowable permutations is m!*n! for a m
by n Matrix.

What I would like to know is if there is one configuration *defineabele*
which I could alwasy reach, regardless with which permutation I start.
The key question is how this end-configuration could be defined, what is
the criteria. Can I define a criteria which gives me for a certain norm
a sort of optimization problem, with a unique endsolution (assuming
there is no symmetry).

In fact this comes from a topological problem. And I try to find a sort
of
a norm for 3D-topologies.

>
> Mikhail
>
> On Wed, 29 Sep 1999, Daniel Heiserer wrote:
>
> > Hi,
> > my question is offtopic, but I think there are enough
> > math-related guys here who might have a nice idea.
> >
> > Assume I have a matrix consisting only of 0 and 1 (sparse).
> > Size is n x m. Where n is nearly m and in  the size of maximum 10000.
> >
> > Each row contains betwen 2 and 8 times "1".
> > Each of the colums contains between 1 and about 10 "1".
> >
> > Now assume I allow to permutate row exchanges as well as column
> > exchanges.
> > ?????????????????????????????????????????????
> > Is there one configuration which is unique (except of some symmetries)?
> > What would be the criteria?
> > Which means for me regarding of which start-configuration I begin
> > I end up with the same end-configuration.
> > Again it is not that I have a criteria, where I look for the "best"
> > solution.
> > I look for a unique solution (except symmertry) and I want to know the
> > criteria for that (e.g. keep the lower left as "0" as possible,
> > or charge off-diagonals by its distance, ....).
> > ?????????????????????????????????????????????
> >
> >
> >
> > ---------------------------------------------------------------------
> > Octave is freely available under the terms of the GNU GPL.  To ensure
> > that development continues, see www.che.wisc.edu/octave/giftform.html
> > Instructions for unsubscribing: www.che.wisc.edu/octave/archive.html
> > ---------------------------------------------------------------------
> >

daniel

---------------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.  To ensure