Diameter of N-Cube

From ProofWiki
Jump to navigation Jump to search


Let $Q_n = \left[{c - R \,.\,.\, c + R}\right]^n$ be an $n$-cube in Euclidean $n$-Space equipped with the usual metric.

Then the diameter of $Q_n$ is given by:

$\operatorname{diam} \left({Q_n}\right) = 2 R \sqrt n$


The diameter of $Q_n$ is the length of some diagonal of $Q_n$



$Q_n = \displaystyle \prod_{i \mathop = 1}^n \left[{c - R \,.\,.\, c + R}\right]_i$

Let $x, y \in Q_n$

By the definition of the usual metric, the distance between any two points $x$ and $y$ is given by:

$\displaystyle d \left({y - x}\right) = \left({\sum_{i \mathop = 1}^n \left({y_i - x_i}\right)^2}\right)^{1 / 2}$

By Positive Power Function on Non-negative Reals is Strictly Increasing, this quantity is maximal when each summand is maximal.

Consider $x_i, y_i$ in the $i$th interval:

$\left[{c - R \,.\,.\, c + R}\right]_i$

To maximize $\left\vert{y_i - x_i}\right\vert$, take $x_i = \min \left[{c - R \,.\,.\, c + R}\right]_i$ and $y_i = \max \left[{c - R \,.\,.\, c + R}\right]_i$.


$\left\vert{y_i - x_i}\right\vert = \left\vert{c + R - \left({c - R}\right)}\right\vert = 2$

By the definition of an $n$-cube, each interval is of the same length.


\(\displaystyle \left({\sup \left({d \left({y - x}\right)}\right)}\right)^2\) \(=\) \(\displaystyle \sup \left({\sum_{i \mathop = 1}^n \left({y_i - x_i}\right)^2 }\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({\sum_{i \mathop = 1}^n \left({2 R}\right)^2}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({2 R}\right)^2 n\) Sum of Identical Terms
\(\displaystyle \) \(=\) \(\displaystyle \left({2 R \sqrt n}\right)^2\)


Proof of Corollary

To minimize the sum in question, we chose each coordinate $y_i$, $x_i$ of $x$ and $y$ to be endpoints.

Thus any $x, y$ so chosen is a vertex, by the definition of vertex.

Certainly $x \ne y$ because were they equal, the distance between them would be zero, and the sum would not be maximal.

The result follows from the definition of a diagonal.