Timeline for The rank of a perturbed triangular matrix
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 8, 2017 at 19:45 | comment | added | Seva | Maybe, you can adapt your code to deal with matrices satisfying the stronger requirement that for any $i,j,k\in[1,n]$, we have $a_{ij}a_{jk}a_{ki}\ne 0$ if and only if $i=j=k$? Say, do there exist such matrices of order $6$ and rank $3$? | |
| Jun 2, 2017 at 19:21 | comment | added | Yoav Kallus | Here is a nice-looking permutation. It's easy to generalize the top 9x9 block to a 3nx3n matrix of rank n+1 with the desired property. It's not immediately obvious to me how the last row and column work. $\begin{array}{cccccccccc}1&0&0&1&0&1&1&0&0&1\\ 0&1&1&0&1&0&-1&0&0&0\\ 1&0&1&0&0&1&0&1&0&0\\ 0&1&0&1&1&0&0&-1&0&1\\ 1&0&1&0&1&0&0&0&1&1\\ 0&1&0&1&0&1&0&0&-1&0\\ 0&0&-1&1&-1&1&1&0&-1&0\\ 1&-1&0&0&-1&1&1&1&0&0\\ 1&-1&1&-1&0&0&0&1&1&0\\ 0&-1&-1&0&0&-1&1&-1&1&1\end{array}$ | |
| Jun 2, 2017 at 4:13 | history | edited | Markus Sprecher | CC BY-SA 3.0 |
removed first example
|
| Jun 2, 2017 at 4:11 | comment | added | Markus Sprecher | There do exist, for example $(i,j)=(7,1)$ and $(i,j)=(6,2)$ | |
| Jun 1, 2017 at 20:19 | comment | added | Seva | BTW, in this your example, again, there do not exist $i,j$ with $a_{ij}=a_{ji}=0$. | |
| Jun 1, 2017 at 19:39 | comment | added | Markus Sprecher | I agree with you and tried to simplify the matrix as much as possible. (However without permutations.) | |
| Jun 1, 2017 at 19:37 | history | edited | Markus Sprecher | CC BY-SA 3.0 |
simplified the -1,0,1 solution
|
| Jun 1, 2017 at 5:53 | comment | added | Seva | It is interesting to see a $\{0,\pm1\}$-solution. This makes me wonder whether there always exists a smallest-possible-rank matrix with all entries in $\{0,\pm1\}$. Another remark is that there are lots of matrices which can be obtained from your matrix by switching the signs of some rows / columns and permuting them (in a coordinated way). It would be extremely interesting to find some "nice" matrix among them, in the hope to grasp and generalize the idea. | |
| May 31, 2017 at 21:25 | history | edited | Suvrit | CC BY-SA 3.0 |
put the matlab code in a pre block
|
| May 31, 2017 at 21:15 | history | edited | Markus Sprecher | CC BY-SA 3.0 |
added -1,0,1 solution+code
|
| May 19, 2017 at 6:02 | comment | added | Markus Sprecher | I parametrized the matrix as $U*V'$ with $U,V\in \mathbb{R}^{n\times r}$ and solved the corresponding system of nonlinear equations. When I had a numerical solution I tried to find integer solutions with the same 0-1 patterns. For this I filled $r$ columns randomly with integers $(-3,..,3)$ and tested if it can be completed to a solution. After a lot of repetions the example above appeared. | |
| May 19, 2017 at 5:55 | history | edited | Markus Sprecher | CC BY-SA 3.0 |
canceled some factors to make the example more appealing
|
| May 19, 2017 at 5:37 | comment | added | Seva | Interesting! This suggests that the lower bound ${\rm rk}\,A\ge\sqrt n$ may be sharp. How did you find this example? I assume you have not checked all matrices with the entries not exceeding 10, say? Are there examples of order $10$ and rank $4$ with all elements in $\{-1,0,1\}$? A very interesting observation is that in your example, as well as in all examples that I found, there is no pair of indices $i,j$ with $a_{ij}=a_{ji}=0$. One last remark is that your example can be slightly simplified by factoring out the common factors from some rows. | |
| May 19, 2017 at 5:33 | history | edited | Seva | CC BY-SA 3.0 |
added 6 characters in body
|
| May 18, 2017 at 21:50 | history | edited | Markus Sprecher | CC BY-SA 3.0 |
deleted 1652 characters in body
|
| May 18, 2017 at 21:45 | history | answered | Markus Sprecher | CC BY-SA 3.0 |