Register to reply

Min number dependent columns in a matrix

by gonzo
Tags: columns, dependent, matrix, number
Share this thread:
gonzo
#1
Oct13-06, 03:12 AM
P: 277
Is there some easy way to determine the minimum number of dependent columns in a matrix? Assume the matrix entries are binary for convenience.

Let's say I have an m x n, m>n matrix in the form (I | A) So that I is nxn, and A is m-n x n. This obviously depends on A.

So is there some easy method for figuring this out by maniuplating A, or is there just a lot of trial and error?
Phys.Org News Partner Science news on Phys.org
Scientists discover RNA modifications in some unexpected places
Scientists discover tropical tree microbiome in Panama
'Squid skin' metamaterials project yields vivid color display
AKG
#2
Oct14-06, 12:10 PM
Sci Advisor
HW Helper
P: 2,586
Row reduction. Look it up.
gonzo
#3
Oct14-06, 12:24 PM
P: 277
Doesn't work. That only gives you the maximum number of independent rows, which is totally different.

Hurkyl
#4
Oct14-06, 12:32 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Min number dependent columns in a matrix

Just to demonstrate more clearly why rank probably won't be too useful... consider the following matrices are all rank 3:

[tex]\left(\begin{array}{cccc}
1 & -1 & 0 & 0 \\
0 & 1 & -1 & 0 \\
0 & 0 & 1 & -1 \\
-1 & 0 & 0 & 1
\end{array}\right)[/tex]

[tex]\left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0
\end{array}\right)[/tex]

[tex]\left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0
\end{array}\right)[/tex]

but the minimum number of rows you need to form a dependent set is 4, 2, and 1 respectively. (4, 1, and 2 if you want a dependent set of columns)
AKG
#5
Oct14-06, 04:47 PM
Sci Advisor
HW Helper
P: 2,586
Oh sorry, I wasn't even paying attention.
Hurkyl
#6
Oct14-06, 05:03 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Yes, I've convinced myself that this is a hard problem in general.

Notice, gonzo, that the problem of finding "the minimum number of dependent columns" is the same as the problem of finding "the most zeroes a nontrivial (right) null vector can have".

If you really want the exact answer, then only approach I can think of at the moment is to compute the intersection of the null space with the various subspaces that have exactly 1 nonzero coordinate, and then with those that have exactly 2 nonzero coordinates, and so forth.
gonzo
#7
Oct15-06, 01:34 AM
P: 277
Yeah, it seems likely to be an very hard problem that gets out of hand fast with big matrices.

I've done a bit more research on this and it seems an active and important area of research, with some people coming up with probablistic algorithms to try and reduce the time for certain classes of matrices.

I feel much better about having trouble with this initially.

By the way, for anyone interested, this number is the minimum distance for the linear code that this matrix is a parity check matrix for.
Hurkyl
#8
Oct15-06, 09:11 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Ah, that I know is hard! Being a parity check matrix makes the problem a little easier, though: it makes it possible to exhaust through all the null vectors, and allows you to represent the problem as a graph.
gonzo
#9
Oct15-06, 09:17 AM
P: 277
Yeah, but even for 15 bits, trying to do it by hand on a test for example can take a lot of time. Like being given the parity check matrix for a [15,5] code and tryingto determine the distance. I had initially hoped for something easier then just trying every combination from the bottom up. Wishful thinking.


Register to reply

Related Discussions
Linearly Independent Columns of a Matrix Linear & Abstract Algebra 4
Finding the greatest number in each row a matrix Programming & Computer Science 3
Complex Number Covariance Matrix General Math 0
Is the severity of a pathogenic illness dependent on the number of pathogens? Biology 2
Linear independence of columns of a matrix Precalculus Mathematics Homework 4