Parallelepiped is defined by the volumes of its faces

Question

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.

Answer 1

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.

Answer 2

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.