Permutation matrices in vector form

1. Oct 28, 2006

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.

2. Oct 29, 2006

AKG

Suppose P has rows R1, ..., Rn. Define q = (R1 ... Rn). q is a 1 x n2 row matrix. As it stands, you have defined p = q, and Y = ppt. This makes Y a 1 x 1 matrix. I suspect that you should either define p = qt and leave Y = ppt, or you should keep p = q but define Y = ptp. Which is it? Well it doesn't really matter, since the resulting Y will be the n2 x n2 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.

3. Oct 29, 2006

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.

4. Oct 29, 2006

AKG

You want to prove vec(PXP') = MtY.
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 Mt? M is diagonal, so M = Mt
The left side of the equation you want to prove is vec(PXP'), which is a 1xn2 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 n2xn2 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.

Last edited: Oct 29, 2006
5. Oct 29, 2006

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.

6. Oct 29, 2006

AKG

No, you defined it such that it would be 1x1, but said that it is n2xn2 despite this.
And initially you said nothing about column-by-column appending, you only mentioned row-by-row, so the p you defined was 1xn2 instead of n2x1. Thus, when you multiplied ppt, you end up with a 1x1 instead of n2xn2, which is Y, as you defined it, really was 1x1.
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 Mt, since M = Mt anyways? If not, then what are they?

Finally, if Mt and Y really are n2xns[up]2[/sup] matrices, then in the equation vec(PXP') = M'Y, the right side is an n2xn2 square matrix. On the left side you get either an n2x1 or a 1xn2 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.

7. Oct 29, 2006

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 cant 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.