
Linear Algebra Linear Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
October 3rd, 2013, 04:21 AM  #1 
Newbie Joined: Oct 2013 Posts: 1 Thanks: 0  Matrix column permutation
Hi, I've got a problem with matrices. I'm working on a project and I've got the following problem: I have 2 matrices, and I need to check if the first one is a columnpermutation of the second. For example: 1 5 8 4 7 9 5 1 8 7 4 9 In this case the algorithm should return true because if I move the second column of the second matrix in first position, I obtain a matrix equals to the first one. Since I'm working with very large matrix, I can't generate all the parmutations of the second matrix, I need to an efficient algorithm. My teacher suggest me to study something on matrix similarity, diagonalization etc... do you have any idea? Thank you very much 
December 31st, 2015, 12:41 PM  #2 
Newbie Joined: Dec 2015 From: Connecticut Posts: 21 Thanks: 4 Math Focus: I love to hate all of them equally 
To start, your algorithm should check to be sure that both matrices have the same shape and that both matrices are not empty. If they do not meet these qualifications, then they cannot be column permutations of each other and your algorithm should return false. One approach is to have your algorithm "cut up" each matrix into its individual column vectors. Test each column vector from the first matrix to make sure it appears as a column vector in the second, and then vice versa. If it passes this test and the one preceding it about shape, then the algorithm should return true. The more mathematical approach is as follows. If the input matrices are column permutations of one another, then multiplying one by a permutation matrix should return the other. A permutation matrix is defined as a square matrix with exactly one entry of 1 in each column and row and entries of 0 everywhere else. The following is an example of a permutation matrix: ( 0 0 1 0 ) ( 1 0 0 0 ) ( 0 0 0 1 ) ( 0 1 0 0 ) Call the input matrices A and B. If A and B are column permutations of each other, then there should exist some permutation matrix P such that AP = B. If A and B are both matrices of the shape m X n, then P should have the shape n X n. Your algorithm should generate all permutation matrices of the shape n X n. It should then perform the operation AP, sequentially checking each possible P. If it finds any P that solves AP = B, it should immediately return true. If it tests all possible P without returning true, then it should return false. Basic Outline:
For your given example, the permutation matrix is: ( 0 1 0 ) ( 1 0 0 ) ( 0 0 1 ) Further reading: Permutation Matrix 

Tags 
column, matrix, permutation 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
question involving matrix row column rank proof  maximus101  Algebra  1  December 31st, 2015 04:45 PM 
Nullity / Column Spaces  playthious  Linear Algebra  1  December 31st, 2015 04:23 PM 
3x4 Matrix with all 0's in the first column  84grandmarquis  Linear Algebra  3  September 22nd, 2013 05:13 AM 
row and column space  wannabe1  Linear Algebra  1  March 18th, 2010 12:38 PM 
3x4 Matrix with all 0's in the first column  84grandmarquis  Algebra  2  December 31st, 1969 04:00 PM 