Timeline for Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17 at 0:54 | vote | accept | Alireza Bakhtiari | ||
| Nov 16 at 8:42 | answer | added | Fedor Petrov | timeline score: 6 | |
| Nov 16 at 5:20 | comment | added | Daniel Weber | Considering the $n \times n$ matrix $A_{ij} = \langle x_i, \theta_j \rangle$, the minimal $d$ which could produce it is exactly the rank of $A$, so the question is what's the minimal rank of a matrix with the given ordering constraints | |
| Nov 16 at 3:26 | answer | added | user527492 | timeline score: 4 | |
| Nov 15 at 4:24 | comment | added | Fedor Petrov | @AlirezaBakhtari consider the vectors $\tau_i:=(\theta_i, 1)\in \mathbb{R}^4$. There is unique linear dependence between them. Thus, the inner product of a vector $(x,-t) \in \mathbb{R}^4$ with $\tau_i$'s may be arbitrary numbers which enjoy the corresponding linear relation | |
| Nov 15 at 4:08 | comment | added | Alireza Bakhtiari | @FedorPetrov Can you explain why "there exists a vector $x$ and real number $t$ such that ..." please? | |
| Nov 15 at 3:07 | comment | added | Fedor Petrov | Next attempt: the only relation is $5\theta_2+\theta_5=2(\theta_1+\theta_3+\theta_4)$ | |
| Nov 15 at 2:36 | comment | added | Fedor Petrov | Oops, I was not correct. | |
| Nov 15 at 1:30 | comment | added | user527492 | @FedorPetrov I'm not sure if I understand the last part of your argument. If $c_4 < c_1 < c_2 < c_3 < c_5$, then $2(c_1 + c_3 + c_5) = 3(c_2 + c_4) < 3(c_3 + c_1)$, which implies $2c_5 < c_3 + c_1 < 2c_5$. | |
| Nov 14 at 6:13 | comment | added | Fedor Petrov | Definitely not $d+1$. For $d=3$ you can choose five theta's so that the only linear relation between them with sum of coefficients 0 is $2(\theta_1+\theta_3+\theta_5)=3(\theta_2+\theta_4)$, then for every 5 real numbers $c_1,c_2,c_3,c_4,c_5$ which enjoy $2(c_1+c_3+c_5)=3(c_2+c_4)$ there exist a vector $x$ and real number $t$ such that $\langle x, \theta_i\rangle=c_i+t$. These $c_i$ may be ordered by all 5 your ways. | |
| Nov 14 at 3:46 | comment | added | Alireza Bakhtiari | Yes. Just put $x_i$'s on a regular simplex and choose $\theta_i$'s that are almost perpendicular to the front face (slight modification is needed). | |
| Nov 14 at 3:35 | comment | added | LSpice | Is $n = d + 1$ always achievable? | |
| Nov 14 at 3:33 | history | edited | LSpice | CC BY-SA 4.0 |
O(d) -> $O(d)$
|
| Nov 14 at 3:10 | history | asked | Alireza Bakhtiari | CC BY-SA 4.0 |