9
$\begingroup$

Let $v_1,...,v_n\in \mathbb{R}^n$ be linearly independent. The parallelepiped defined by these vectors is $P(v_1,...,v_n)=\{\sum_{i=1}^{n}\alpha_i v_i|~0\le\alpha_i\le 1\}$. Observe that while the collection $v_1,...,v_n$ is reconstructible from $P(v_1,...,v_n)$ as a subset of $\mathbb{R}^n$, it is not reconstructible from $P(v_1,...,v_n)$ as a geometric figure. Indeed, if $U$ is an orthogonal operator on $\mathbb{R}^n$, then $P(Uv_1,...,Uv_n)=UP(v_1,...,v_n)$ is isometric to $P(v_1,...,v_n)$. Moreover, $P(v_1,...,-v_i,...,v_n)$ is a translate of $P(v_1,...,v_n)$ by $-v_i$. You can also view this as the shift of origin: instead of looking from the point $0$ we are now looking from the vertex $v_i$. In fact $P(\pm v_1,...,\pm v_n)$ correspond to every of $2^{n}$ vertex of this parallelepiped.

For $A=\{i_1,...,i_k\}\subset\{1,...,n\}$ define $V(A)=V_k(P(v_{i_1},...,v_{i_k}))$, where $V_k$ is the $k$-dimensional volume.

Let $w_1,...,w_n\in \mathbb{R}^n$ also be linearly independent, and for $A\subset\{1,...,n\}$ define $W(A)$ analogously.

I can show the following

Proposition. If $W(A)=V(A)$ for every $A\subset\{1,...,n\}$, then $P(w_1,...,w_n)$ and $P(v_1,...,v_n)$ are isometric, i.e. there are $a_1,...,a_n=\pm 1$ and an orthogonal operator $U$ on $\mathbb{R}^n,$ such that $w_i=a_iUv_i$, for every $i$.

However, I can only do it using a result about principal minors of a symmetric matrix determining it up to multiplying both $i$-th row and $i$-th column by $\pm 1$ (in our case we consider the Gram matrices, whose principal minors are exactly the squares of the corresponding volumes).

Is the Proposition known? Is there a geometric proof of it?

I tried to build a proof on the fact that we know the distance from every $v_i$ to the span of any other combination of $v_j$ (including the empty one), but geometry kind of gets intertwined with combinatoric of what is orthogonal to what, and I got stuck.

PS In fact the Proposition is equivalent the result that I've mentioned (in the real case), and it is proven e.g. here:

Rising, Justin; Kulesza, Alex; Taskar, Ben, An efficient algorithm for the symmetric principal minor assignment problem, Linear Algebra Appl. 473, 126-144 (2015). ZBL1314.65050.

$\endgroup$
5
  • $\begingroup$ Is $P(v_1, \ldots, -v_k, \ldots, v_n)$ really a translation by $-2 v_k$? I would have expected $P(v_1 - v_k, \ldots, v_k - 2 v_k, \ldots, v_n - v_k)$. As for the claim that $P(\pm v_1, \ldots, \pm v_k)$ correspond to the vertices, that looks odd as well. There are $n$ vertices but $2^n$ combinations of $\pm$'s. $\endgroup$ May 13, 2018 at 8:37
  • $\begingroup$ Here's a thought: if we look just at the $1$-dimensional cases, i.e, the $W(\{i_1, i_2\}) = V(\{i_1, i_2\})$ then we see that the two shapes have congruent sides and all the diagonals. Since two triangles are congruent if they have the same lengths of sides, we should be able to get a proof from this observation. Or is my sense of rigidity betraying me in higher dimensions? $\endgroup$ May 13, 2018 at 8:40
  • 1
    $\begingroup$ A theorem of Minkowski is applicable. See Theorem 36.2 of math.ucla.edu/~pak/geompol8.pdf. $\endgroup$ May 13, 2018 at 14:36
  • $\begingroup$ @RichardStanley so do I understand correctly that you suggest to consider all $2n$ vectors $\pm 1v_i$ and apply Minkowski's theorem to them? But still, how do we know that there is an orthogonal operator that takes the set $\{v_i, -v_i\}$ into the set $\{w_i, -w_i\}$? We do know that $|\left<v_i,v_j\right>|=|\left<w_i,w_j\right>|$, but I don't see how to finish the proof. $\endgroup$
    – erz
    May 14, 2018 at 8:03
  • $\begingroup$ @AndrejBauer I was indeed wrong about the vector of translation: it should be just $v_k$. As for the second claim, the parallelepiped has $2^n$ vertices (e.g. $n$-dimensional cube). Also, we really need to use all the information, I'll provide a counterexample if needed. However, I did try something along the lines that you suggest, and I really hope it is possible to fins a proof like that. $\endgroup$
    – erz
    May 14, 2018 at 8:26

2 Answers 2

2
$\begingroup$

Here is a geometric proof of the result. $\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\be}{\boldsymbol{e}}$ As I comment at the end of the proof, this actually proves a stronger fact.

Define two equivalence relations"$\sim_n$" and "$\approx_n$" on the set of bases of $\bR^n$.

$$ (v_1,\dotsc, v_n)\sim_n (w_1,\dotsc, w_n) $$

$\DeclareMathOperator{\vol}{vol}$ $\newcommand{\eps}{\epsilon}$ if for any subset $I\subset \{1,\dotsc, n\}$ we have $$ \vol(v_i, \;\;i\in I)=\vol(w_i,\;\;i\in I) $$ and $$ (v_1,\dotsc, v_n)\approx_n (w_1, \dotsc, w_n) $$ if there exists orthogonal map $T$ and scalars $\eps_i=\pm 1$ such that

$$ w_i= \eps_iTv_i,\;\;\forall i=1,\dotsc , n. $$ $\newcommand{\Llra}{\Longleftrightarrow}$ The result states that $\sim_n \Llra \approx_n$. Clearly $\approx_n\implies \sim_n$.

Clearly $\sim_1\Llra \approx_1$. We then argue by induction. Assume $\sim_n\Llra \approx_n$. To prove that $\sim_{n+1}\Llra \approx_{n+1}$ it suffices to show that if

$$(v_0, v_1,\dotsc, v_n)\sim _{n+1} (w_0, v_1,\dotsc, v_n), $$

then

$$(v_0, v_1,\dotsc, v_n)\approx_{n+1} (w_0, v_1,\dotsc, v_n). $$

$\DeclareMathOperator{\span}{span}$ $\DeclareMathOperator{\Proj}{Proj}$ For $I\subset \{1,\dotsc, n\}$ we set

$$ V_I:=\span\{v_i;\;\;i\in I\}. $$

and for any vector $u$ we denote by $[u]_I$ its orthogonal projection on $V_I$.

Since $vol(v_0, v_i, i\in I)=\vol(w_0, v_i, I\in I)$, $\forall I\subset \{1,\dotsc, n\}$ we deduce

$$\big\Vert\; v_0-[v_0]_I\;\big\Vert =\Big\Vert\; w_0-[w_0]_I\;\big\Vert. $$ Pythagoras' Theorem implies

$$ \big\Vert\;[v_0]_I\;\big\Vert =\big\Vert\;[w_0]_I\;\big\Vert. \tag{$\ast$} $$

Since $$ \vol(v_0,v_i)=\vol(w_0,v_i),\;\;\forall i=1,\dotsc, n, $$ there exists $\eps=\pm 1$ such that

$$ (v_0,v_i)=\eps(w_0,v_i), $$ where $(-,-)$ denotes the inner product. We set $$ S_i:=\big\{\; \eps=\pm 1;\;\; (v_0,v_i)=\eps(w_0,v_i)\;\big\}. $$

Remark. Above, the two inner products are simultaneously nonzero or simultaneously zero. When they are zero $S_i=\{-1,1\}$. Note that $|S_i|=1$ iff $(v_0,v_i)\neq 0$.

Lemma 1. If $i\neq j$ and $(v_i,v_j)\neq 0$, then $S_i\cap S_j\neq \emptyset$.

Proof. For simplicity assume $i=1, j=2$. If $(v_0,v_1)=(v_0,v_2)=0$ then $(w_0,v_1)=(w_0,v_2)=0$ and the result is obviously true. Suppose that $(v_0,v_1)\neq 0$. Denote by $\be_1,\be_2$ the orthonormal basis of $\span(v_1,v_2)$ obtained from the basis $v_1,v_2$ via Gram-Schmidt. Then

$$ v_1=x\be_1,\;\; v_2=y\be_1+z\be_2 $$ where $x,z>0$ and $y\neq 0$ since $(v_1,v_2)\neq 0$. Write

$$a_1=(v_0,\be_1),\;\;a_2=(v_0,\be_2), $$ $$ b_1=(w_0,\be_1),\;\;b_2=(w_0,\be_2). $$

Then $a_1=\eps_1 b_1=(v_0,v_1)\neq 0$. Since $a_1^2+a_2^2=b_1^2+b_2^2$ we deduce $a_2=\pm b_2$. We want to show that $a_2=\eps_1 b_2$. Let $a_2=\eta_2b_2$, $\eta_2=\pm 1$. We want to prove that $\eps_1\in S_2$. We argue by contradiction. We have

$$ (v_0,v_2)=\eps_2(w_0,v_2),\;\;\eps_2\neq \eps_1, $$ so that, given that $a_1=\eps_1b_2$, we get

$$ a_1y+a_2 z=\eps_2\eps_1a_1 y+\eps_2\eta_2 a_2z $$ Since $\eps_2\neq \eps_1$ we have $\eps_2\eps_1=-1$ and we deduce

$$2 a_1y= (\eps_2\eta_2-1)a_2z\neq 0 $$

so $a_2\neq 0$ and $\eta_2\eps_2=-1$, i.e., $\eta_2=\eps_1 $ and $b_2=\eps_1 a_2$ and $(w_0,v_2)=\eps_1(v_0,v_2)$. $\Box$

We now define a graph $\Gamma$ with vertices $\{1,\dotsc, n\}$ where two distinct vertices $i,j$ are connected by an edge if $(v_i,v_j)\neq 0$. Denote by $\Gamma_1,\dotsc, \Gamma_c$ its connected components. Let $I_\alpha$ denote the set of vertices of $\Gamma_\alpha$. We obtain an orthogonal decomposition

$$ V:=\span(v_1,\dotsc, v_n)=\bigoplus_{\alpha} V_{I_\alpha}. $$

For any vector $u$ we set $$ [u]_\alpha:=[u]_{I_\alpha}. $$

Lemma 2. Suppose that $i,j$ belong to the same component $\Gamma_\alpha$ and $|S_i|=1$. Then $S_i\subset S_j$.

Proof. $\DeclareMathOperator{\dist}{dist}$ We argue by induction on the distance $\dist_{\Gamma_\alpha}(i,j)$. The case $\dist_{\Gamma_\alpha}(i,j)=1$ is covered by Lemma 1.

We assume the result is true whenever $\dist(i,j)<d$ and we prove that it is true when $\dist(i,j)=d$.

For simplicity we assume that $i=1$ and $v_1,v_2,\dotsc, v_{d+1}=v_j$ is a path of length $d$ in $\Gamma_\alpha$ connecting $i$ to $j$.

If there exists $k$, $1<k<d+1$ such that $(v_0,v_k)\neq 0$ then $|S_k|=1$, $\dist(v_i,v_k), \dist(v_k,v_j)<d$ and the induction assumption implies

$$ S_i\subset S_k\subset S_j.$$

Since $v_1,\dotsc, v_{d+1}$ is a minimal path connecting $i$ to $j$ we deduce that for any $1\leq k<\ell \leq d+1$, $\ell-k\geq 2$, the vertices $v_j,v_\ell$ are not adjacent so $(v_k, v_\ell)=0$.

Consider the orthonormal basis $\be_1,\dotsc,\be_{d+1}$ of $\span\{v_1,\dotsc, v_{d+1}\}$ obtained from $v_1,\dotsc, v_{d+1}$ via Gram-Schmidt. Then

$$v_1=c_{01}\be_1,\;\;v_2=c_{12}\be_1+c_{02}\be_2,\;\;v_k=c_{1k}\be_{k-1}+c_{0k}\be_k,\;\;k=2,\dotsc, d+1, $$

$$c_{0k}>0,\;\;c_{1k}\neq 0. $$

We denote by $v_0'$ and $w_0'$ the orthogonal projections of $v_0$ and respectively $w_0$ on $\span\{v_1,\dotsc, v_{d+1}\}$.

Then

$$v_0'=\sum_{k=1}^{d+1} a_k\be_k,\;\; w_0'=\sum_{k=1}^{d+1} b_k\be_k. $$

From ($\ast$) we deduce $a_k=\pm b_k$, $\forall k$. Moreover, $a_1=(v_0,v_1)\neq 0$. For simplicity we assume that $a_1=b_i$, i.e. $S_i=S_1=\{1\}$. We have to prove that $1\in S_{d+1}$ i.e.,

$$(v_0, v_{d+1})= (w_0, v_{d+1}). $$

For $k=2,\dotsc, d$ we have

$$ a_{k-1}c{1k}+a_k c_{0k}=(v_0,v_k)=0=((w_0,v_k)=b_{k-1}c_{1k}+b_kc_{0k} $$

and we deduce that

$$a_k=b_k\neq 0,\;\;\forall k=1,\dotsc, d. $$

If $1\in S_{d+1}$ we are done. If $-1\in S_{d+1}$, then

$$ a_dc_{1,d+1}+a_{d+1} c_{0,d+1}=(v_0,v_{d+1})=-(w_0, v_{d+1})=-a_dc_{1,d+1}-b_{d+1} c_{0,d+1}, $$

so that

$$0\neq 2a_dc_{1, d+1}=-(a_{d+1} +b_{d+1}) c_{0,d+1}. $$

Hence $a_{d+1}+b_{d+1}\neq0$ so $a_{d+1}=b_{d+1}$ and thus

$$(v_0, v_{d+1})=(w_0, v_{d+1}), $$

i.e., $1\in S_{d+1}$. $\Box$

Corollary 3. For any $\alpha=1,\dotsc, c$ there exists $\eps_\alpha=\pm 1$ such that

$$[v_0]_\alpha=\eps_\alpha[w_0]_\alpha. $$

Proof. If $v_0\perp v_i$, $\forall i\in I_\alpha$ the result is obvious since in this case $[v_0]_\alpha=[w_0]_\alpha=0$.

Suppose that $(v_0,v_i)\neq 0$ so that $S_i=\{\eps_i\}$, $\eps_i=\pm 1$. Using Lemma 2 we deduce that $S_i\subset S_j$, $\forall j\in I_\alpha$.

We can take $\eps_\alpha=\eps_i$. $\Box$

Choose a unit vector $\be_0\in\bR^{n+1}$ such that $\be_0\perp V=\span\{v_1,\dotsc, v_n)$. Then we have an orthogonal decomposition

$$ v_0=a_0\be_0+\sum_\alpha[v_0]_\alpha,\;\;w_0=b_0\be_0+\sum_\alpha [w_0]_\alpha. $$

There exists $\eps_0=\pm 1$ such that $a_0=\eps_0b_0$. Define the orthogonal map $T:\bR^{n+1}\to\bR^{n+1}$ $\newcommand{\bone}{\boldsymbol{1}}$

$$T=\eps_0\bone_{\span\be_0}\oplus \bigoplus_\alpha\eps_\alpha\bone_{V_{I_\alpha}}. $$

Then $Tv_0=w_0$ and $Tv_i=\eps_\alpha v_i$ for $i\in V_\alpha$. $\Box$

Remark. The connected components $\Gamma_\alpha$ used in the above proof have a nice geometric interpretation.

For any $I\subset \{1,\dotsc, n\}$ we denote by $G_I$ the group of orthogonal transformations $T$of $V_I$ such that $Tv_i=\pm v_i$, $\forall i\in I$. Clearly $\pm \bone_{V_I}\subset G_I$. The set $I$ is called irreducible if $G_I=\{\pm \bone_{V_I}\}$.

Note that if two irreducible sets $I,J$ are not disjoint, then their union is also irreducible. Thus, every $i=1,\dotsc, n$ is contained in a unique maximal irreducible subset and we obtain a partition of $\{1,\dotsc, n\}$ into maximal irreducible sets. These maximal irreducible sets are precisely the vertex sets of the components $\Gamma_\alpha$.

Comment. It seems to me that requiring the knowledges of the volumes of all faces is too strong a condition. There are $2^n-1$ faces whereas a basis is determined by $n^2$ numbers. Note that the set of bases of $\bR^n$ modulo the action of $O(n)$ is a space of dimension

$$ n^2-\frac{ n(n-1)}{2}=\frac{n(n+1)}{2}=n+{n \choose 2}. $$

This suggests that, the result ought to be true under weaker assumptions.

$\endgroup$
10
  • $\begingroup$ I am still halfway through your answer, but your claim seems incorrect to me: consider the case when $n=3$ and $v_i=e_i$, $1\le i\le 3$ with $v_0=e_0+e_1+e_2$ and $w_0=e_0+e_1-e_2$ (only two dimensions matter here). Then $[v_0]_2=e_1+e_2$, while $[w_0]_2=e_1-e_2$. $\endgroup$
    – erz
    May 14, 2018 at 22:27
  • $\begingroup$ I'm sorry, but I still don't understand: with the same example $[v_0]_3=e_1+e_2$, while $[w_0]_3=e_1-e_2$, and they are not co-linear. I think that the argument that you use several times about equality of $\eta_i$ is incorrect as $T$ in the example above is neither $Id$, nor $-Id$ when restricted to the span of $e_1$ and $e_2$. In my opinion, this is exactly the fundamental difficulty - we cannot really fix the transformation on the $n$ vectors and only tweak $n+1$-th (if I understand correctly what is happening). $\endgroup$
    – erz
    May 15, 2018 at 3:47
  • $\begingroup$ You are correct. I'll ttry to fix the argument. $\endgroup$ May 15, 2018 at 13:37
  • $\begingroup$ I've fixed the argument. $\endgroup$ May 16, 2018 at 9:22
  • $\begingroup$ It seems that your proof is more or less based on the same idea as mine, and is also the more directly computational proof from the article. Probably there is just no way around considering the components of non-orthogonality. $\endgroup$
    – erz
    May 16, 2018 at 21:06
1
$\begingroup$

This is a quasi-geometrical proof. After finding it I've realized that it is somewhat similar to the combinatorial-computational proof in the article that I've mentioned. Let $H$ be a real inner product space. We will call a finite sequence $u_1,...,u_n\in H$ a chain (from $u_1$ to $u_n$) if $u_{i}\bot u_{j}$ whenever $|i-j|>1$ and $u_i\not\bot u_{i+1}$. We need two lemmas:

Lemma 1. Let $u_1,...,u_n\in H$ be a chain. Then $u_1,...,u_{n-1}$ are linearly independent.

Proof. We will show that $u_k\not\in \mathrm{span}\{u_1,...,u_{k-1}\}$ for every $1<k<n$. Assume that $u_k=\alpha_1 u_1+...+\alpha_{k-1} u_{k-1}$, where $1<k<n$. Then each of $u_1,u_2,...,u_{k-1}$ are perpendicular to $u_{k+1}$, and so $u_k\bot u_{k+1}$, which contradicts the definition of chain.

Lemma 2. Let $B\subset H$ be linearly independent. Let $u,w\in \mathrm{span}B$ be such that for any $A\subset B$ we have $u_A\bot w_A$, where $u_A$ and $w_A$ are the projection of $u$ and $v$ respectively on $\mathrm{span}A$. Then there is a partition $B=B_u\sqcup B_w$ such that $B_{u}\bot B_{w}$ and $u\in \mathrm{span}B_{u}, w\in\mathrm{span}B_{w}$.

Proof. Define $B_u$ to be the set of all $v\in B$ such that there is a chain from $u$ to $v$ from elements of $B$, and $B_w=B\backslash B_u$.

In order to prove proposition it is enough to show that if $u_1,...,u_n,w_1,...,w_m\in B$ are such that $u_0=u,u_1,...,u_n$ and $w_0=w,w_1,...,w_m$ are chains, then $u_n\bot w_m$. We will use the induction by $m+n$. When $m+n=0$ this follows from $u_0=u=u_B\bot w_B=w=w_0$.

Assume the claim holds for $m+n$ and assume that $A=\{u_1,...,u_n,u_{n+1},w_1,...,w_m\}\subset B$ are such that $u_0=u,u_1,...,u_n,u_{n+1}$ and $w_0=w,w_1,...,w_m$ are chains. Then, from the hypothesis of induction $u_i\bot w_j$, when $i\le n$. Let $u'\bot v'$ be the orthogonal projections of $u,w$ on $\mathrm{span}A$. Then $u'\bot u_i$ for $i>2$ and $u'\bot w_i$. Hence, $u'\not\bot u_1$, and so $u',u_1,...,u_n,u_{n+1}$ is a chain. Analogously, $w',w_1,...,w_m$ is also a chain.

Note that $u',u_1,...,u_n\in \{w',w_1,...,w_m\}^{\bot}$. All these $m+n+2$ vectors belong to span of the linearly independent collection $A$, whose dimension is $m+n+1$. By Lemma 1, $u',u_1,...,u_n$ are linearly independent, as well as $w',w_1,...,w_{m-1}$, and so $w_m\in \mathrm{span}\{w',w_1,...,w_{m-1}\}$. Since all of the vectors in the span are perpendicular to $u_{n+1}$, we conclude that $u_{n+1}\bot w_m$.


After having Lemma 2 let's prove the Proposition by induction: it is enough to show that if $v_1,...,v_n$ are linearly independent in $\mathbb{R}^{n+1}$ and $v_0,v_{n+1}\in \mathbb{R}^{n+1}$ are such that for any $\{i_1,...,i_k\}\subset\{1,...,n\}$ the $k+1$-dimensional volumes of $P(v_{n+1},v_{i_1},...,v_{i_k})$ and $P(v_0,v_{i_1},...,v_{i_k})$ is the same, then there $a_1,...,a_n=\pm 1$ and an orthogonal operator $T$ on $\mathbb{R}^{n+1},$ such that $v_i=a_iTv_i$, for every $i\in\overline{1,n}$ and $v_{n+1}=Tv_0$.

Let $v'_0$ and $v'_{n+1}$ be the projections of $v_0$ and $v_{n+1}$ on $\mathrm{span}\{v_1,...,v_n\}$. Note that $\|v_0-v'_0\|=\|v_{n+1}-v'_{n+1}\|$. Also let $2u=v'_0+v'_{n+1}$ and $2w=v'_0-v'_{n+1}$. Then $u,w$ satisfy the conditions of the Lemma. Indeed, the projection of $v'_0=u+v$ and $v'_{n+1}=u-v$ on the span of any combination of $v_i$ have equal length, and $\|Pr~u+Pr~v\|=\|Pr~u-Pr~v\|$ implies $Pr~u\bot Pr~v$.

By Lemma 2 we can find $1\le k\le n$ and relabel $v_1,...,v_n$ so that $v_1,...,v_k\bot v_{k+1},...,v_{n}$ and $u\in \mathrm{span}\{v_1,...,v_k\},~w\in \mathrm{span}\{v_{k+1},...,v_n\}$.

Now define $T$ by:

  • $Tv_1=v_1,...,Tv_k=v_k$ (from which it follows that $Tu=u$);
  • $Tv_{k+1}=-v_{k+1},...,Tv_n=-v_n$ (from which it follows that $Tw=-w$);
  • $T(v_0-v'_0)=v_{n+1}-v'_{n+1}$; then $Tv_0=T(v_0-v'_0)+Tu+Tw=v_{n+1}-v'_{n+1}+u-w=v_{n+1}$.

Since $T$ restricted to $\mathrm{span}\{v_1,...,v_k\}$, $\mathrm{span}\{v_{k+1},...,v_n\}$ and $\{v_1,...,v_n\}^{\bot}$ is orthogonal, and these subspaces are also mutually orthogonal, we see that $T$ is an orthogonal. Thus, $T$ satisfies all the desired properties.

$\endgroup$
2
  • $\begingroup$ But, of course, a paralellogram is not determined by the lengths of its sides... $\endgroup$ May 15, 2018 at 21:58
  • $\begingroup$ @GeraldEdgar sorry, what do you mean? We have more data: the whole parallelogram also is considered a face, and so we know the area. Parallelogram is determined by the area and the lengths of its sides $\endgroup$
    – erz
    May 16, 2018 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.