My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Reply
 
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 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
Blanco is offline  
 
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:
  1. Test if inputs are of the same shape. If they are not, return false.
  2. Test if inputs are empty. If they are, return false.
  3. Generate all possible n X n permutation matrices.
  4. Perform matrix right multiplication on A by P. Iterate until this operation generates B. If B is generated, return true.
  5. 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
Brachydactyloid is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

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





Copyright © 2019 My Math Forum. All rights reserved.