matrix question
- From: "marv" <marv742@xxxxxxxxxxxx>
- Date: 11 May 2006 19:15:04 -0700
Hi,
Consider the following problems. Let x_i i=1..N and y_i i=1..N be
integer-valued sequences. I want to find a permutation p of {1..N} s.t.
x_p(i) = y_i (or prove that no such permutation exists). This is easy
enough, just sort the values {x_1, x_2, ... x_N} and {y_1, y_2, .. ,
y_N} and see if the two sets are the same (including multiplicities).
Now suppose I have two matrices X_{i,j} and Y_{i,j} again with integer
entries. I'm looking for an algorithm which finds a column permutation
c, and a row permutation r s.t. X_{r(i), c(j)} = Y_{i,j} (or proves
non-existence). Can this be done in polynomial time in N?
Next, I have triply-subscripted quantities X_{i,j,k} and Y_{i,j,k} and
I now seek three permutations which map X to Y as before. Is this
solvable in polynomial time?
Marv
.
- Follow-Ups:
- Re: matrix question
- From: Igor Khavkine
- Re: matrix question
- From: M.J.T. Guy
- Re: matrix question
- From: Carlos Moreno
- Re: matrix question
- Prev by Date: Re: new self-published book
- Next by Date: M-Primary
- Previous by thread: what does 'determinant Δ' mean
- Next by thread: Re: matrix question
- Index(es):
Relevant Pages
|
