Timeline for Sorting a binary matrix diagonal in polynomial time while preserving rows
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 11, 2010 at 21:15 | comment | added | Gerhard Paseman | Related is the following: If the matrix A has nonzero determinant (over the integers), then such a diagonal will exist and can be gotten by row permutations alone. However, if A has nonzero determinant , has sufficiently many rows, AND there is at least one zero in every row and in every column, it is possible that no permutation of rows or columns or both will place all zeros on the diagonal. Gerhard "Ask Me About System Design" Paseman, 2010.08.11 | |
| Aug 11, 2010 at 20:43 | comment | added | Will Jagy | Tracy, might that mean there is a greedy algorithm for the case when there is a solution with all 1's on the diagonal? | |
| Aug 11, 2010 at 20:29 | comment | added | Tracy Hall | In particular, there is a solution with every diagonal entry 1 if and only if every time you remove all but $k$ columns, you still have at least $k$ nonzero rows. | |
| Aug 11, 2010 at 19:11 | comment | added | Will Jagy | en.wikipedia.org/wiki/Assignment_problem | |
| Aug 11, 2010 at 18:23 | comment | added | Will Jagy | I see, an "optimal assignment problem" where the final row $i$ gets the current contents $P(i)$ and the cost function is simply nonzero constant for a 0 in $(i,i)$ and cost zero for a 1 in $(i,i).$ The way I learned it you have workers as rows and jobs as columns, and a cost assigned to each square. So this needs some fiddling to be programmed properly but should work, and rapidly. | |
| Aug 11, 2010 at 18:15 | history | answered | Aaron Meyerowitz | CC BY-SA 2.5 |