Timeline for Permutation similarity of matrices with many distinct entries
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 26, 2023 at 15:26 | comment | added | joro | @NathanielJohnston Thanks. Related question with code: mathoverflow.net/questions/449492/… | |
| Jun 9, 2023 at 18:11 | history | rollback | Rodrigo de Azevedo |
Rollback to Revision 1
|
|
| Jun 9, 2023 at 18:10 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
added 1 character in body
|
| Jun 9, 2023 at 14:22 | comment | added | Nathaniel Johnston | If the diagonal entries are all distinct (so, e.g., if $k = n^2$) then this can be done in polynomial time by noticing that $PAP^T = B$ forces $A$ and $B$ to have the same diagonal entries (not necessarily in the same order) and there is only one permutation that could possibly work: the one that re-arranges the diagonal entries of $A$ to match the order of those of $B$. A similar argument gives a polynomial-time method for $k \geq n^2 - c$, where $c$ is constant. | |
| Jun 9, 2023 at 12:35 | history | asked | joro | CC BY-SA 4.0 |