How to write an hyperplane as $\{x \in \Bbb R^d \mid c^T x = \beta\}$ given the vectors spanning it.

23 Views Asked by At

I was reading "Lectures on 0/1-Polytopes" by Ziegler and at one point, it says :

Let $\{0, v_1, . . . , v_{d−1}\} ⊆ \{0, 1\}^d$ be points that span a hyperplane $H$ in $\Bbb R^d$, and let $V = (v_1, . . . , v_{d−1})^T ∈ \{0, 1\}^{(d−1)×d}$. Then an equation that defines $H$ is given by $c^Tx = 0$, with $c_i = ± \det(V_i)$, where $V_i ∈ \{0, 1\}^{(d−1)×(d−1)}$ is obtained from $V$ by deleting the $i$-th column.

but I don't understand why it is true. By the way, is it a more general result or does it only work with 0/1 spanning vectors ? (Although I don't see why it would only work with 0/1 vectors)

1

There are 1 best solutions below

0
On BEST ANSWER

In general, if $v_1,\ldots,v_{d-1} \in \mathbb{R}^{d-1}$ are linearly independent, their span is a $(d-1)$-dimensional subspace (hyperplane) $H$ that that can be written as $H = \{x : c^\top x =0\}$, where $c$ is any nonzero vector that is perpendicular to each of $v_1,\ldots,v_{d-1}$.

Thus in your problem, you need to check $v_i^\top c = 0$ for each $i$. If you consider doing the dot product $v_i^\top c$, you can see that it is computing the determinant of the $d \times d$ matrix $(v_i, v_1,\ldots,v_{d-1})^\top$ by doing the Laplace expansion along the first row. This $d \times d$ matrix is obviously not full rank, so the determinant is zero, and thus we indeed have $v_i^\top c = 0$.

Thus, your problem does not rely on the fact that you are considering binary vectors.

Note that your construction of $c$ is not the only way; another approach would be to do the Gram-Schmidt process on $v_1,\ldots,v_{d-1}$.