1) Whether a matrix is a column permutation of another matrix. Recall that I only use column interchanges.

2) Whether a matrix has an all-one diagonal.

3) Whether a zero block, say of dimension r x s, is a zero block of a matrix, say with dimension n x n, and whether r + s > n. Yes, my implementation specifies such a zero block if no all-one diagonal can be attained.

The algorithm appeared correct for millions of matrices.

Remark that the first part of your labeled phase corresponds to the "B has only zero's"-part of the greedy phase on M2 (now I think of it, the greedy phase can be reduced to the "B has only zero's"-part at this point). Maybe, both algorithms only differ in their formulation. Your inductional B, which may be higher than its width, corresponds to the B-part of M2.

I formulated the greedy part differently as well. I interchange pairs of columns if that improves the diagonal (by one or two extra 1's). This way, both parts of the greedy phase are unified.

Last night, someone pointed me coincidentally that he had read a test for determining whether a number is a power of 2. I formulated
!(a & (a - 1))
which seemed even more efficient than the test he read:
(a & -a) == a
Yes, both tests have a bug that 0 is seen as a power of 2. If we look at my test, we see that a & (a-1) removes the least significant bit of a. So a - (a & (a-1)) selects the least significant bit'set. But I do not see how to get the index (exponent) of that bit fast. An idea is to loop on bytes rather that bits and use table lookup for the bytes. On an Intel 386 or better, you can get this index with the BSF instruction (bit scan forward). 1 << BSF(a) is also a way to get the least significant bit. With BSF, there is no need to make the matrix smaller in the inductional steps in order to gain efficiency. Unfortunately, I implemented my algorithm on a Sparc. But probably, these machine level considerations are not very interesting to you; at least they do not belong on your web page.

In case you prefer my algorithm, my surname is "De Bondt". "de" has no capital when preceded by a first name or initials; it means "the".

Michiel

Dear Michiel:

It's not a question of choosing preferences. Prof. McWorter amended his proof in two ways. He expanded the last paragraph of the proof but also added a remark before the proof to the effect that the case when the number of girls equals the number of boys may be equal without loss of generality. Indeed, if there are more girls than boys, the marriage condition is violated. If there are more boys than girls, a few girls can be added to equate the quantities. Such an operation will not affect the marriage condition provided the add-on girls agree to marry any boy.

Following the path of least resistance, I accept William's modifications.

I applaud your involvement and ingenuity.

Alex

> In case you prefer my algorithm,
> my surname is "De Bondt". "de" has
> no capital when preceded by a first
> name or initials; it means "the".

The "you" in the second paragraph refers to the "we" in the first. So you do not need to choose, Mr. Bogomolny. I sent another reply with a discussion on the presentation of the algorithm, but I can not find in back on the forum. I think it is important that the algorithm is presented clearly; any name associated with it does not interest me at all.

Michiel

You mean it got misplaced. I apologize if it did. Please check the thread.

>I think
>it is important that the algorithm is presented clearly;

Absolutely.

I sent you the above reply three times, but I think the second time got lost again. In the last attempt, I had [code]d the figures to get them correct. So it would be nice if you replace the above by it. I have registered myself in order to be able to attach files, which I tried, but it did not work. So I put it below, but now with all layout details, I hope.

Michiel

GREEDY PHASE:

| 1         |       |
|   1       |       |
|     .     |   D   |
|       .   |       |
|         1 |       |
|-----------|-------|
|           |       |
|     C     |   B   |
|           |       |
 A                   

If block B is empty (0 by 0), then we are done, the family has a SDR. If B contains a 1, interchange rows through C and columns through D of A to put a 1 in the upper left corner of B. Next, replace B with the matrix obtained by using all but the first row and first column of B, replace C and D accordingly, and resume the greedy phase.

So we finally arrive at an empty B or a B with only zero entries.

B HAS ONLY ZEROS:

| 1         |       |
|   1       |       |
|     .     |   D   |
|       .   |       |
|         1 |       |
|-----------|-------|
|           |       |
|     C     |   0   |
|           |       |
 A                   

If block C has only zeros, we are done; the family has no SDR because the sets associated with the columns through C together with a set associated with a column through D violate the marriage condition; that is, the union of these sets contains one fewer elements than the number of sets.

So assume that C has at least one 1. Let E be the columns of C that contain a 1. Interchange corresponding pairs of rows and columns of A to reach the following figure:

| 1     |       |       |
|   .   |       |   H   |
|     1 |       |       |
|-------|-------|-------|
|       | 1     |       |
|       |   .   |   G   |
|       |     1 |       |
|-------|-------|-------|
|       |       |       |
|   0   |   E   |   0   |
|       |       |       |
 A                      

If a_ij = 1 in block E and a_jk = 1 in block G, then interchange columns j and k of A and resume the greedy phase with B the lower right corner block which now contains a 1.

Otherwise, G has only zeros. If H has only zeros as well, then the set corresponding to any column through G violates the marriage condition.

LABELED PHASE:

| 1     |       |       |
|   .   |       |   H   |
|     1 |       |       |
|-------|-------|-------|
|       | 1     |       |
|   F   |   .   |   0   |
|       |     1 |       |
|-------|-------|-------|
|       |       |       |
|   0   |   E   |   0   |
|       |       |       |
 A                      

Having reached here, every column of E contains a 1 and H does not only contain zeros. If the block F contains only zeros, then we are done; the family has no SDR because the sets corresponding to the columns through F and one column through H violates the marriage condition.

If for every nonzero column of F, the corresponding row of H has only zeros, then let E₁ be the nonzero columns of F and let G₁ be the rows of H corresponding to the columns of E₁. Interchange corresponding pairs of rows and columns to get

| 1     |       |           |           |
|   .   |       |           |     H1    |
|     1 |       |           |           |
|-------|-------|-----------|-----------|
|       | 1     |           |           |
|   F1  |   .   |           |     G1    |
|       |     1 |           |           |
|---------------|-----------|-----------|
|       |       | 1         |           |
|       |       |   1       |           |
|   0   |   E1  |     .     |     0     |
|       |       |       .   |           |
|       |       |         1 |           |
|---------------|-----------|-----------|
|               |           |           |
|               |           |           |
|       0       |     E     |     0     |
|               |           |           |
|               |           |           |
 A                                      

If G₁ has a 1, then we can interchange a column through G₁ with a column through E₁ to put a 1 in the zero block G just below G₁, whence we can do another column interchange to put a 1 into the lower right block B of A and resume the GREEDY PHASE.

Otherwise, G₁ has only zero entries. If F₁ has only zeros, then, as with F, the sets corresponding to the columns of F₁ and one set corresponding to a column of G₁ violate the marriage condition. Otherwise, let E₂ be the nonzero columns of F₁. Interchange corresponding pairs of rows and columns to reach

| 1 |   |       |           |     H2    |
|---|---|-------|-----------|-----------|
| F2| 1 |       |           |     G2    |
|-------|-------|-----------|-----------|
|   |   | 1     |           |           |
| 0 | E2|   .   |           |     0     |
|   |   |     1 |           |           |
|---------------|-----------|-----------|
|       |       | 1         |           |
|       |       |   1       |           |
|   0   |   E1  |     .     |     0     |
|       |       |       .   |           |
|       |       |         1 |           |
|---------------|-----------|-----------|
|               |           |           |
|               |           |           |
|       0       |     E     |     0     |
|               |           |           |
|               |           |           |
 A                                      

If G₂ contains a 1, we can do a series of column swaps to put a 1 to the right of E and resume the GREEDY PHASE. Otherwise, if F2 contains only zero entries, then the sets corresponding to the columns through F2 and one set corresponding to a column through G₂ violate the marriage condition.

Otherwise, we continue the construction of E_i's, F_i's, G_i's and H_i's until some G_i has a nonzero entry (in which case we do a series of swaps that puts a 1 to the right of E and resume the GREEDY PHASE) or some F_i has only zero's (in which case the marriage condition is violated). Since H has at least one 1, this process stops before we reach a H_i with zero rows.

[Example:

          1 0 0 0 1
          1 1 0 0 0
          0 1 1 0 0
          0 0 1 1 0
          0 0 0 1 0

A series of 4 swaps needed to put a 1 in the lower right corner.]

Thanks again for your help in clarifying things.
William

My last reply IS your algorithm. MY algorithm can be found in the first message of this thread, but has already been rejected, essentially by yourself when you updated the page on the marriage algorithm. Both algorithms are not that much different and I do not prefer one over the other.

What I think is more important is that the algorithm is presented clearly. That is why I tried to clarify your proof, which resulted in my previous reply. Since you still recognize your own algorithm and think my clarifications look good, it'seems a good idea to apply them. However, with your name above the algorithm, your approval is required.

Michiel