Return to Answer

A proof from matrix theory

Let $V=(v_1,...,v_m)\in\Bbb R^{n\times m}$ be the matrix with the $v_i$ as columns (and let us assume that $\|v_i\|=1$). The matrix $X:=V^\top V\in\Bbb R^{m\times m}$ has the following properties:

• $X$ is positive semi-definite, that is, all eigenvalues are real and $\ge 0$. Furthermore, the multiplicity of the eigenvalue zero is equal $m-d$, wehre $d$ is the rank of $X$ and equals $d:=\dim \mathrm{span}\{v_1,...,v_m\}\le n$.
• $X_{ij}=v_i\cdot v_j$, in particular, the diagonal of $X$ consists of 1-s, and the off-diagonal entries of $X$ are negative.

The matrix $Y:=2I-X$ has only positive entries, and by Perron-Frobenius, its maximal eigenvalue has therefore multiplicity one. Hence, the minimal eigenvalue of $X$ has multiplicity one. Thus, the multiplicity of zero as eigenvalue of $X$ is at most one (it could be that zero is not an eigenvalue at all, but if it is one, it is the smallest).

Consequently, $m-d\le1\implies m\le d+1\le n+1$.

A proof from matrix theory

Let $V=(v_1,...,v_m)\in\Bbb R^{n\times m}$ be the matrix with the $v_i$ as columns (and let us assume that $\|v_i\|=1$). The matrix $X:=V^\top V\in\Bbb R^{m\times m}$ has the following properties:

• $X$ is positive semi-definite, that is, all eigenvalues are real and $\ge 0$. Furthermore, the multiplicity of the eigenvalue zero is equal $m-d$, where $d$ is the rank of $X$ and equals $d:=\dim \mathrm{span}\{v_1,...,v_m\}\le n$.
• $X_{ij}=v_i\cdot v_j$, in particular, the diagonal of $X$ consists of 1-s, and the off-diagonal entries of $X$ are negative.

The matrix $Y:=2I-X$ has only positive entries, and by Perron-Frobenius, its maximal eigenvalue has therefore multiplicity one. Hence, the minimal eigenvalue of $X$ has multiplicity one. Thus, the multiplicity of zero as eigenvalue of $X$ is at most one (it could be that zero is not an eigenvalue at all, but if it is one, it is the smallest).

Consequently, $m-d\le1\implies m\le d+1\le n+1$.

A proof from matrix theory

Let $V=(v_1,...,v_m)\in\Bbb R^{n\times m}$ be the matrix with the $v_i$ as columns. The matrix $X:=V^\top V\in\Bbb R^{m\times m}$ has the following properties:

• $X$ is positive semi-definite, that is, all eigenvalues are real and $\ge 0$. Furthermore, the multiplicity of the eigenvalue zero is equal $m-d$, wehre $d$ is the rank of $X$ and equals $d:=\dim \mathrm{span}\{v_1,...,v_m\}\le n$.
• $X_{ij}=v_i\cdot v_j$, in particular, all off-diagonal entries of $X$ are negative.

The matrix $Y:=I-X$ has only positive entries, and by Perron-Frobenius, its maximal eigenvalue has therefore multiplicity one. Hence, the minimal eigenvalue of $X$ has multiplicity one. Thus, the multiplicity of zero as eigenvalue of $X$ is at most one (it could be that zero is not an eigenvalue at all, but if it is one, it is the smallest).

Conclusively $m-d\le1\implies m\le d+1\le n+1$.

A proof from matrix theory

Let $V=(v_1,...,v_m)\in\Bbb R^{n\times m}$ be the matrix with the $v_i$ as columns (and let us assume that $\|v_i\|=1$). The matrix $X:=V^\top V\in\Bbb R^{m\times m}$ has the following properties:

• $X$ is positive semi-definite, that is, all eigenvalues are real and $\ge 0$. Furthermore, the multiplicity of the eigenvalue zero is equal $m-d$, wehre $d$ is the rank of $X$ and equals $d:=\dim \mathrm{span}\{v_1,...,v_m\}\le n$.
• $X_{ij}=v_i\cdot v_j$, in particular, the diagonal of $X$ consists of 1-s, and the off-diagonal entries of $X$ are negative.

The matrix $Y:=2I-X$ has only positive entries, and by Perron-Frobenius, its maximal eigenvalue has therefore multiplicity one. Hence, the minimal eigenvalue of $X$ has multiplicity one. Thus, the multiplicity of zero as eigenvalue of $X$ is at most one (it could be that zero is not an eigenvalue at all, but if it is one, it is the smallest).

Consequently, $m-d\le1\implies m\le d+1\le n+1$.

Let $V=(v_1,...,v_m)\in\Bbb R^{n\times m}$ be the matrix with the $v_i$ as columns. The matrix $X:=V^\top V\in\Bbb R^{m\times m}$ has the following properties:

• $X$ is positive semi-definite, that is, all eigenvalues are real and $\ge 0$. Furthermore, the multiplicity of the eigenvalue zero is equal $m-d$, wehre $d$ is the rank of $X$ and equals $d:=\dim \mathrm{span}\{v_1,...,v_m\}\le n$.
• $X_{ij}=v_i\cdot v_j$, in particular, all off-diagonal entries of $X$ are negative.

The eigenvalues of $Y:=I-X$ are $\le 1$. But $Y$ has only positive entries, and by Perron-Frobenius, its maximal eigenvalue has therefore multiplicity one. This means the zero as eigenvalue of $X$ has multiplicity at most one (it could be that zero is not an eigenvalue at all, but if it is one, it is the smallest).

Conclusively $m-d\le1\implies m\le d+1\le n+1$.

A proof from matrix theory

Let $V=(v_1,...,v_m)\in\Bbb R^{n\times m}$ be the matrix with the $v_i$ as columns. The matrix $X:=V^\top V\in\Bbb R^{m\times m}$ has the following properties:

• $X$ is positive semi-definite, that is, all eigenvalues are real and $\ge 0$. Furthermore, the multiplicity of the eigenvalue zero is equal $m-d$, wehre $d$ is the rank of $X$ and equals $d:=\dim \mathrm{span}\{v_1,...,v_m\}\le n$.
• $X_{ij}=v_i\cdot v_j$, in particular, all off-diagonal entries of $X$ are negative.

The matrix $Y:=I-X$ has only positive entries, and by Perron-Frobenius, its maximal eigenvalue has therefore multiplicity one. Hence, the minimal eigenvalue of $X$ has multiplicity one. Thus, the multiplicity of zero as eigenvalue of $X$ is at most one (it could be that zero is not an eigenvalue at all, but if it is one, it is the smallest).

Conclusively $m-d\le1\implies m\le d+1\le n+1$.