User Name Remember Me? Password

 Linear Algebra Linear Algebra Math Forum

 October 3rd, 2013, 03: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 column-permutation 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, 11:41 AM #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:Test if inputs are of the same shape. If they are not, return false. Test if inputs are empty. If they are, return false. Generate all possible n X n permutation matrices. Perform matrix right multiplication on A by P. Iterate until this operation generates B. If B is generated, return true. If all P are tested and B is not produced, return false. 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post maximus101 Algebra 1 December 31st, 2015 03:45 PM playthious Linear Algebra 1 December 31st, 2015 03:23 PM 84grandmarquis Linear Algebra 3 September 22nd, 2013 04:13 AM wannabe1 Linear Algebra 1 March 18th, 2010 11:38 AM 84grandmarquis Algebra 2 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top

Copyright © 2019 My Math Forum. All rights reserved.      