Permutation matrices in vector form

[vix_cse]

hi all

I have a simple question relating to permutation matrices.

We have an a matrix, X. We have a permutation matrix, P. We can get the permuted version of X by doing
permutedX = P*X*P'.
Now, I want to represent the matrices in vector form. The way the books mention it as follows.
They define vectors p = vec(P) by putting each row of P one after the other. Then constructing Y = p*transpose(p). So, P is of size n by n and Y is of size n^2 by n^2. they then construct vec(X) and define a matrix M of size n^2 by n^2 by putting elements of vec(X) on its main diagonal. The following statement confuses me.
M*Y is equivalent to the first equation,
I tried doing this in MATLAB considering P to be a simple identity matrix of size 3 by 3. does not work. i am possibly missing something really simple. can somebody tell me how this reasoning works.

thanks.

 

[AKG]

Suppose P has rows R₁, ..., R_n. Define q = (R₁ ... R_n). q is a 1 x n² row matrix. As it stands, you have defined p = q, and Y = pp^t. This makes Y a 1 x 1 matrix. I suspect that you should either define p = q^t and leave Y = pp^t, or you should keep p = q but define Y = p^tp. Which is it? Well it doesn't really matter, since the resulting Y will be the n² x n² matrix you intend it to be.

Next, MY isn't an equation, so how can it be equivalent to the first equation? And what is the first equation? I would have to assume you mean permutedX = PXP', but you haven't defined "permutedX" or "P'" so no one can help you.

 

[vix_cse]

hi.
What I meant by equivalence is that
vec(P*X*P')==transpose(M)*Y
I want to know if this statement is true or not. As before P is a n by n perm matrix, X is a n by n matrix. Y=vec(P)*vec(P)' which is n^2 by n^2 and M=vec(X) which is n^2 by 1. If this does not hold, can we do the same using something else?

I want to know a form where the X (or M) can be multiplied by a single matrix say Y1 and the result will be same as P*X*P' or vec(P*X*P'). So I want to determine Y1 as a function of P.

thanks.

 

[AKG]

You want to prove vec(PXP') = M^tY.
P is a permutation nxn matrix.
X is any nxn matrix.
M is a diagonal matrix whose diagonal elements are elements of vec(X) [so the kth element of vec(X) occurs at the k,k position in M?].
Y = vec(P)vec(P)'.
vec(A) for any matrix A is found by putting the rows of A one after another.

So what is P'? I mean, what does the ' symbol do?
Why bother looking at M^t? M is diagonal, so M = M^t
The left side of the equation you want to prove is vec(PXP'), which is a 1xn² row matrix, as you've defined it. Y is a 1x1 matrix as you've defined it. So the right side of your equation is an n²xn² matrix multiplied by a 1x1 matrix, which is impossible. Please recheck your definitions. I already asked you to do this, please pay attention this time and answer all the questions asked.

 

[vix_cse]

hi.

I think I already defined Y to be n^2 by n^2 (read my first post). i am sorry if you got the impression that Y is of size 1 by 1. By P', I wanted to say transpose(P). Matlab does it this way. You can construct p from P by considering rows/columns appended one after the other. If P is a n by n matrix, p is n^2 by 1 (assuming you do column by column appending). Either way, the idea is clear. I am forming a matrix Y of size n^2 by n^2 from the vector representations of P.

Now, say I want to permute an input matrix X. In standard matrix form, I could do
permutedX = P*X*P' where P' is transpose(P).
now, say I want to represent this in a form where the right hand side is the product of two terms only, say M*Y. How do I go about doing this? This is my only question.
The papers I looked at say:
define M to be vec(X). then, do M'*Y where Y is defined to be p*p' where p is a column vector of size n^2 by 1 and p' is its transpose of size 1 by n^2.

i'll be glad if you could shed some light on this or suggest an alternate way.

thanks.

 

[AKG]

hi.

I think I already defined Y to be n^2 by n^2 (read my first post). i am sorry if you got the impression that Y is of size 1 by 1.

No, you defined it such that it would be 1x1, but said that it is n²xn² despite this.

By P', I wanted to say transpose(P). Matlab does it this way. You can construct p from P by considering rows/columns appended one after the other. If P is a n by n matrix, p is n^2 by 1 (assuming you do column by column appending).

And initially you said nothing about column-by-column appending, you only mentioned row-by-row, so the p you defined was 1xn² instead of n²x1. Thus, when you multiplied pp^t, you end up with a 1x1 instead of n²xn², which is Y, as you defined it, really was 1x1.

Either way, the idea is clear.

It makes a big difference depending on which way you do it.

Okay, since you're having trouble being clear, just explain what you want vec(P) to be if P were:

(1 2 3)
(4 5 6)
(7 8 9)

I know that's not a permutation matrix, but just demonstrate the construction of vec(P) from P. You have the following options:

vec(P) = (1 2 3 4 5 6 7 8 9)
vec(P) = (1 4 7 2 5 8 3 6 9)
vec(P) = (1 2 3 4 5 6 7 8 9)^t
vec(P) = (1 4 7 2 5 8 3 6 9)^t

Now you say M has the elements of vec(X) on its diagonal. Okay, what about the rest of the elements of M? Are the rest all zero? If so, then why does your equation look at M^t, since M = M^t anyways? If not, then what are they?

Finally, if M^t and Y really are n²xns[up]2[/sup] matrices, then in the equation vec(PXP') = M'Y, the right side is an n²xn² square matrix. On the left side you get either an n²x1 or a 1xn² row or column matrix (depending on the definition of vec(PXP'), which you still haven't given clearly), so the left side can't possibly equal the right side.

 

[vix_cse]

hi.

if P were:

(1 2 3)
(4 5 6)
(7 8 9)

vec(P) would be vec(P) = (1 4 7 2 5 8 3 6 9)^t.

M is a matrix with the elements of vec(X) on its diagonal and 0 everywhere else. In notations, M = Diag(vec(X)). For simplicity, we can assume that M is binary.

I think we were having trouble because there were inconsistencies in the matrix sizes.What I am trying to do is simple but I can't get it to work. I have an input matrix X. I permute it by doing P*X*P'. ok?
Now, I want to represent the same thing with the requirement that I can only work with X and P in vector form (1 by n^2 or n^2 by 1 etc) and eventually recover P*X*P'.

So, I represent p = vec(P) as above. then constructed Y = vec(P)*vec(P)' and constructed M with elements of vec(X) on its diagonal. how do it proceed from here to recover P*X*P'?

if there are still doubts with notations ignore them as long as you understand the problem.

thanks.