Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Each $B_i$ can have two non-zero rows/columns, so it is possible that all rows/columns of $\sum_i B_i$ are non-zero. But the matrix is still sparse and has no more than 4n elements.
Can semidefinite optimisation achieve the optimal complexity? To my knowledge, optimization based methods typically give an approximate solution rather than exact one and the complexity depends on the desired error $\epsilon$. Could you please give some reference for related problems? Thank you!
@JochenGlueck Thanks! It seems that your answer along with Ulam Mazur theorem proves both questions 1 and 3. Do I understand correctly? Also, I notice that if $\mathbb R^n$ is replaced by $\mathbb C^n$, the mapping will not be restricted to be linear. Does it mean in this case there might exist other non-trivial distance-preserving mappings for general norm? (I guess problem may be hard in this setting)
Thanks for pointing in out. I am aware that it may be hard to exclude such a case. Nevertheless, I am most interested in $L_p$ norm (and also the last question).
