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 have the following problem which is a part of a larger problem. I would like to hear your comments or point me to the correct direction.

I am making use of a randomly generated boolean matrix of size $K\times N$. I am not following any strict procedure to introduce the randomness. I know the rank of this matrix is $K$.

I am wondering if there is any way for me to reduce the value $N$ ( since $K$ is fixed) so that the rank of the matrix is till $K$. I basically want to reduce the size from $K \times N$ to $K \times (N-\text{some number})$.

I am assuming I can do this by increasing the randomness in the matrix generated. Or is there a better way of doing this ?

EDIT 1: I actually do know that when i find the K linearly independent columns i can reduce the size of the generator matrix form $K \times N$ to $K \times K$ maybe I should have clarified this earlier on. I actually want to reduce the size of the original generator matrix to $K \times N-\text{a Number}$ ( so that I need to perform fewer calculations in order to find the $K$ linearly independent columns from the original generator matrix)

share|improve this question
The largest number of linearly independent columns is still $K$ (since it equals the rank of the matrix). So... what do you mean by "many more linearly independent columns"? Reducing the number of columns will likely reduce the number of subsets that are linearly independent, and will not, in any case, increase the size of the largest set. –  Arturo Magidin Feb 16 '12 at 6:07
@ArturoMagidin well maybe i should try this with examples. Right now I have a matrix of size 10X29 from where I get 10 linearly independent columns. I want to reduce this to 10X12 where I still have 10 linearly independent columns is there any way to do this. May be i remove that part of the question does not seem to make too much sense –  bhavya Feb 16 '12 at 6:21
Yes, of course you can reduce it: find 10 linearly independent columns, and remove any other 17 columns. You can find 10 linearly independent columns by performing Gaussian row-reduction on the matrix; identify the columns in the row-reduced matrix that have the leading coefficients, and the corresponding columns in the original matrix are linearly independent. –  Arturo Magidin Feb 16 '12 at 6:24
Indeed, you can reduce to 10-by-10 by finding 10 linearly independent columns and removing all of the other 19 columns. –  Gerry Myerson Feb 16 '12 at 6:29
Search for puncturing a code. The matrix can be viewed as the generator matrix of a (random) $[N,K]$ linear binary code ($K$-dimensional subspace of $N$-dimensional binary space), and deleting columns while still maintaining the row rank at $K$ corresponds to deleting parity-check symbols of the code, reducing the length of the codewords while keeping the same number of codewords, which operation is picturesquely called puncturing the code by coding theorists. I guess it means letting some of the "useless" hot air of parity symbols out. –  Dilip Sarwate Feb 16 '12 at 18:57

Your Answer


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

Browse other questions tagged or ask your own question.