Permutation matrices in vector form

In summary, the conversation discusses the construction of a permuted version of a matrix using a permutation matrix and representing matrices in vector form. The process involves constructing a vector p by appending the rows of the permutation matrix P and then creating a matrix Y by multiplying p and its transpose. This method is used to represent the permuted matrix in the form of M*Y, where M is a diagonal matrix constructed from the vector representation of the original matrix X. However, there is confusion in the conversation regarding the size and construction of Y and the correct way to define vec(P) from P.
  • #1
vix_cse
7
0
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.
 
Physics news on Phys.org
  • #2
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
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
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:
  • #5
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
vix_cse said:
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 n2xn2 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 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.
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 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
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.
 

Related to Permutation matrices in vector form

1. What is a permutation matrix in vector form?

A permutation matrix in vector form is a square matrix where each row and column contains exactly one 1 and all other entries are 0. It represents a permutation in the form of a vector, where the position of the 1 in each row corresponds to the position of the element that is being permuted in the original vector.

2. How is a permutation matrix in vector form used in linear algebra?

Permutation matrices in vector form are used to perform permutations on vectors in linear algebra. They are often used in conjunction with other linear algebra operations, such as matrix multiplication, to efficiently rearrange the elements of a vector.

3. Can a permutation matrix in vector form be used to permute any vector?

Yes, a permutation matrix in vector form can be used to permute any vector. It is a general representation of a permutation and can be applied to any vector regardless of its length or elements.

4. How is a permutation matrix in vector form created?

A permutation matrix in vector form can be created by rearranging the columns of an identity matrix. The columns are rearranged according to the desired permutation. Alternatively, it can also be created by using elementary row operations on a matrix with the rows representing the elements in the original vector.

5. What is the inverse of a permutation matrix in vector form?

The inverse of a permutation matrix in vector form is its transpose. This is because a permutation matrix is an orthogonal matrix, meaning its inverse is equal to its transpose. Therefore, to reverse the permutation, the rows and columns of the matrix are simply swapped, resulting in the original vector.

Similar threads

Replies
7
Views
881
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
704
Replies
27
Views
1K
Replies
7
Views
2K
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
6
Views
969
  • Linear and Abstract Algebra
Replies
1
Views
965
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
4
Views
969
Back
Top