the distinguished matrix

[BMAD]

Imagine you have several distinguishable rows composed of several distinguishable columns

The intersection of the rows and columns either have a 1 or a 0.

Each row sums to the same value and the question is how many of the columns can you eliminate assuming the the 1's in each row are randomly distributed across the columns

Example, there are 30 rows and 20 columns with each row containing 7 randomly dispersed 1's. How many columns can be eliminated reducing the total in each row by no more than 2.

[CaptainEd]

After elimination of columns, do the row totals all still have to be equal (although maybe equal to 6 or 5?)

[BMAD]

No they just need to be distinguishable.

Edited June 1, 2018 by BMAD

[bonanova]

This sounds a lot, but not exactly, like eliminating variables from sets of equations. Is that the idea?

[BMAD]

On 6/4/2018 at 6:00 AM, bonanova said:

This sounds a lot, but not exactly, like eliminating variables from sets of equations. Is that the idea?

yes.

[CaptainEd]

Scratching the surface...

when we start, the average column sum is 210/20 = 10.5

we are moving from row sums of 7 down to row sums no less than 5. This implies we are removing columns totaling no more than 60. So a rough estimate of the number of columns removed is 60/10.5, or roughly 6.

Another way of visualizing this argument is to imagine the first step in the removal. Pick a row, pick two of the 7 1-cells, and remove those columns. Now, to avoid reducing this row sum below 5, we must “freeze” the other 5 columns. 

Now pick another row, and two of its 7 1-cells, and remove those two columns. Now we have removed four columns, and frozen 10. There are only 6 left, so we can do the same once more, resulting in 6 columns removed.

I admit, there might be some overlap between frozen columns, so that there might be more than 6 columns left after removing four columns, but it seems like at least 6 can be removed.

[CaptainEd]

While this doesn’t answer the question with randomly placed 1s, I think it does give an upper bound to the number of columns that can be removed.

What is the smallest number of remaining columns that would allow (a) the 30 rows to be distinct, (b) each row to have 5 1-bits, and (c) all remaining columns to be distinct?

7 columns: 7!/2!5! = 21, too few distinct rows
8 columns: 8!/3!5! = 56, that’s enough.

The first 12 columns in each of the 30 rows should be one of these patterns:
11000 00000 00 
01100 00000 00
00110 00000 00
00011 00000 00
00001 10000 00

00000 11000 00
00000 01100 00
00000 00110 00
00000 00011 00
00000 00001 10

00000 00000 11
10000 00000 01

The last 8 columns should be chosen from the C(8,5) possible patterns.

The resulting matrix satisfies the requirements because:
(a) the last eight columns differentiate the 30 rows
(b) the first twelve columns are distinct by design
(c) the last eight columns are distinct because of the distinct patterns chosen from the C(8,5)
(d) all row sums are 7 before column removal, and 5 afterwards

[BMAD]

On 12/11/2018 at 9:00 PM, CaptainEd said:

While this doesn’t answer the question with randomly placed 1s, I think it does give an upper bound to the number of columns that can be removed.

 

  Hide contents

 

What is the smallest number of remaining columns that would allow (a) the 30 rows to be distinct, (b) each row to have 5 1-bits, and (c) all remaining columns to be distinct?

7 columns: 7!/2!5! = 21, too few distinct rows
8 columns: 8!/3!5! = 56, that’s enough.

The first 12 columns in each of the 30 rows should be one of these patterns:
11000 00000 00 
01100 00000 00
00110 00000 00
00011 00000 00
00001 10000 00

00000 11000 00
00000 01100 00
00000 00110 00
00000 00011 00
00000 00001 10

00000 00000 11
10000 00000 01

The last 8 columns should be chosen from the C(8,5) possible patterns.

The resulting matrix satisfies the requirements because:
(a) the last eight columns differentiate the 30 rows
(b) the first twelve columns are distinct by design
(c) the last eight columns are distinct because of the distinct patterns chosen from the C(8,5)
(d) all row sums are 7 before column removal, and 5 afterwards

 

 

I agree