Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've created a program which solves any matrix (rows contain one element more than columns) by using Gaussian method. Matrix can be as small as $6\times5$ and as large as $101\times100$. So far I have only found one case when program fails. It does so if there is one or more 0 on diagonal.

Example:

$$\begin{pmatrix}a&b&c\\d&e&f\\g&h&i&\end{pmatrix}$$ Elements d and h can't be equal to 0 (zero). Every other element can be negative, zero or positive.

What I want to do is swap columns and rows of the matrix as until:

  • 1 there are no more zeros on diagonal, which means program can proceed
  • 2 Program has run out of combinations, which means given matrix can't be solved by only using Gaussian method and swapping rows and columns.

Point #2 has my interest right now. How can I get all combinations of a matrix by only swapping rows and columns?

Matrix like this: $$\begin{pmatrix}a&b\\d&e\end{pmatrix}$$

has 4 combinations (?) if only swapping of rows and columns is allowed.

$$\begin{pmatrix}a&b\\d&e\end{pmatrix}$$ $$\begin{pmatrix}c&d\\a&b\end{pmatrix}$$ $$\begin{pmatrix}d&c\\b&a\end{pmatrix}$$ $$\begin{pmatrix}b&a\\d&c\end{pmatrix}$$

2*2 matrix has  4 combinations
2*3 matrix has 12 (2*3*2) combinations
3*3 matrix has 36 (6*2*3) combinations (not 100% sure...)
3*4 matrix has 144 (6*6*4) combinations (not 100% sure...)

I think that there probably exists an algorithm which could be used to swap rows and columns of the matrix until there are no more combinations left.

share|improve this question
    
I only know of one procedure to solve such matrices by using Gaussian method. My program is supposed to be an exact implementation of how I solve the given matrix on paper. I have implemented all steps I'd do with pen and paper, except for row/column swapping. If I had a matrix with 0 on subdiagonal and I had to solve it on paper, row/column swapping would be the easiest/fastest solution. I would only need a couple swaps, obviously. So, to make sure matrix is solvable by this specific method, I want to go through all combinations. –  afaf12 Sep 29 '11 at 6:26
4  
Look up "pivoting" or "Gaussian elimination with pivoting", which is the usual way of dealing with this. Trying all combinations is a bad idea, as it is very slow. –  Yuval Filmus Sep 29 '11 at 6:38
    
In fact, for the most part, linear system solvers do only row swaps and no column swaps (the problems where column swaps absolutely must be done is quite small, thankfully) since doing column swaps take too much overhead. –  J. M. Sep 29 '11 at 10:32
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.