Obtaining a permutation associated to a matrix

sagequstions
243 ●6 ●9 ●18

Let $A$ be an invertible $n \times n$ matrix and denote by $r_i(A,j)$ the vector with entries as in row $i$ of $A$ with columns from $1,...,j$ . We can obtain $r_i(A,j)$ in Sage as follows:

def givesubmatrix(A,i,j):
    B=A[[i-1],[0..j-1]]
    return(B)

I want to find the permutation $p(A)$ of the set $\{ 1,...,n \}$ (it seems set brackets dont work in this forum using latex? So I use [ and ] instead for the set brackets) defined by the condition:

$p(A,i):=\min \{ j \mid r_i(A,j) \text{ is not in the span of } \{r_1(A,j),...,r_{i-1}(A,j) \} \}.$

Is there an easy way to obtain this permutation?

I have already problems to define the subspace generated by $\{r_i(A,j),...,r_{i-1}(A,j) \}$ using Sage.

Comments

Latex works fine here, but you need to double each backslash - e.g. use \\{ for opening brace $\{$ .

Max Alekseyev ( 0 years ago )

Thank you, I did not know this. I do not have to do this when I use texmaker or overleaf.

sagequstions ( 0 years ago )

Btw, you don't need to create lists like [0..j-1] unless they are truly needed, it's more efficient to use generators like (0..j-1).

Max Alekseyev ( 0 years ago )

add a comment

answered 0 years ago

Max Alekseyev

6922 ●9 ●52 ●161

updated 0 years ago

This should do the job:

def riAj(A,i,j):
    return A.row(i-1)[:j]

def pAi(A,i):
    for j in (1..A.ncols()):
        if A[0,j-1]!=0 and riAj(A,i,j) not in span(A.base_ring(),(riAj(A,k,j) for k in (1..i-1))):
            return j
    raise ValueError

link

Comments

Thank you! Is there a problem in your code to calculate the value of the permtuation at i=1? For the matrix A=matrix([[0,-1],[1,-1]]) , I get the "wrong" permutation [1,1] using your code and my code to get the complete permutation:

def permutationofmatrix(A):
    n=A.nrows()
    W=[pAi(A,i) for i in [1..n]]
    return W

I think p(A,1) should be the smallest j such that $a_{1,j} \neq 0$ . In the example we should have p(A,1)=2, but your code gives $p(A,1)=1$ .

sagequstions ( 0 years ago )

I've added this condition to the code

Max Alekseyev ( 0 years ago )

Now it seems to return a constant number for each i. A=matrix([[0,0,0,-1],[0,0,1,-1],[0,1,0,-1],[-1,1,1,-1]]) gives [4,4,4,4] as permutation.

sagequstions ( 0 years ago )

I think it is better to just modify the first entry in the definition. I did this and here is the code to get the permutation:

def riAj(A,i,j):
return A.row(i-1)[:j]

def pAi(A,i):
    for j in (1..A.ncols()):
        if riAj(A,i,j) not in span(A.base_ring(),(riAj(A,k,j) for k in (1..i-1))):
            return j
    raise ValueError



def permutationofmatrix(A):
    n=A.nrows()
    U=[t for t in [0..n-1] if A[0,t]!=0]
    t=min(U)+1
    W1=[t]
    W2=[pAi(A,i) for i in [2..n]]
    return W1+W2

It seems it works fine now. Thanks again!

sagequstions ( 0 years ago )

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Obtaining a permutation associated to a matrix

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Obtaining a permutation associated to a matrix savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Obtaining a permutation associated to a matrix