Skip to main content
corrected mistake; proved stronger result; included conjecture for best possible result.
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\}))$$$$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\})),\quad \theta=\min(\{\theta_i\})$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i)$$$$\beta_i=\frac{\pi}{2}-\angle(p,x_i),\quad\beta=\max(\{\beta_i\})$$

CLAIM. If $\theta_i\ge \theta>0$ for every $i$, then there is at least one $i$ such that $\displaystyle \beta_i\ge \frac{\theta}{n}$. $$\sin(\beta)\ge\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}$$

PROOF. Trivial if $\theta=0$, so assume $\theta>0$. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $\theta>0$ implies that $X$ beingis invertible implies, therefore

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) ThisMoreover $x'_j \perp x_i$ for $j\ne i$ also implies $\text{span}(\{x'_j \;|\; j\ne i\}$ is the hyperplane orthogonal to $x_i$, and thus $\angle(x'_i,\text{span}(\{x'_j\;|\; j\ne i\}))=\angle(\text{span}(\{x_j \;|\; j\ne i\}),x_i)=\theta_i$ and then $\angle(x'_i,x'_j)\ge \max(\theta_i,\theta_j)\ge \theta$. In conclusion

$$\displaystyle |c_{ij}|\le \frac{1}{\sin(\theta)^2}$$$$\displaystyle |c_{ij}|\le \frac{\cos(\theta)}{\sin(\theta)^2}\quad\text{if } i\ne j$$ $$\displaystyle |c_{ii}|\le \frac{1}{\sin(\theta)^2}$$

and therefore if $\beta=\max\{\beta_i\}$ $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \frac{n^2\sin(\beta)^2}{\sin(\theta)^2}$$$$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \sin(\beta)^2\frac{n+(n^2-n)\cos(\theta)}{\sin(\theta)^2}$$ $$\sin(\beta)\ge\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}$$

whichThis also implies $\sin(\beta)\ge \sin(\theta)/n$, andthe good $\beta\ge \theta/n$ by monotonicity of(as $\sin(x)/x$ in$\theta\rightarrow 0$) first order approximation $[0,\pi/2]$$\sin(\beta)\ge \sin(\theta)/n$. $\quad\blacksquare$

I verified empirically that $\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}\ge \sin(\frac{\theta}{n})$, which would imply $\beta\ge\frac{\theta}{n}$ too, but I'll leave the proof of that as an exercise, if true.

The example in my other answer shows this result isled me to conjecture that the best possible, in first order result should be $$\sin(\beta)\ge \sin(\theta)\sqrt{\frac{(n-1)\tan(\theta)^2+n}{n((n-1)\tan(\theta)^2+n^2)}}$$

which is not much stonger than the claim, as $\theta\rightarrow 0$but probably much harder to prove.

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\}))$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i)$$

CLAIM. If $\theta_i\ge \theta>0$ for every $i$, then there is at least one $i$ such that $\displaystyle \beta_i\ge \frac{\theta}{n}$.

PROOF. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $X$ being invertible implies

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) This implies

$$\displaystyle |c_{ij}|\le \frac{1}{\sin(\theta)^2}$$

and therefore if $\beta=\max\{\beta_i\}$ $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \frac{n^2\sin(\beta)^2}{\sin(\theta)^2}$$

which implies $\sin(\beta)\ge \sin(\theta)/n$, and $\beta\ge \theta/n$ by monotonicity of $\sin(x)/x$ in $[0,\pi/2]$. $\quad\blacksquare$

The example in my other answer shows this result is best possible, in first order, as $\theta\rightarrow 0$.

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\})),\quad \theta=\min(\{\theta_i\})$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i),\quad\beta=\max(\{\beta_i\})$$

CLAIM. $$\sin(\beta)\ge\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}$$

PROOF. Trivial if $\theta=0$, so assume $\theta>0$. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $\theta>0$ implies that $X$ is invertible, therefore

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) Moreover $x'_j \perp x_i$ for $j\ne i$ also implies $\text{span}(\{x'_j \;|\; j\ne i\}$ is the hyperplane orthogonal to $x_i$, and thus $\angle(x'_i,\text{span}(\{x'_j\;|\; j\ne i\}))=\angle(\text{span}(\{x_j \;|\; j\ne i\}),x_i)=\theta_i$ and then $\angle(x'_i,x'_j)\ge \max(\theta_i,\theta_j)\ge \theta$. In conclusion

$$\displaystyle |c_{ij}|\le \frac{\cos(\theta)}{\sin(\theta)^2}\quad\text{if } i\ne j$$ $$\displaystyle |c_{ii}|\le \frac{1}{\sin(\theta)^2}$$

and therefore $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \sin(\beta)^2\frac{n+(n^2-n)\cos(\theta)}{\sin(\theta)^2}$$ $$\sin(\beta)\ge\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}$$

This also implies the good (as $\theta\rightarrow 0$) first order approximation $\sin(\beta)\ge \sin(\theta)/n$. $\quad\blacksquare$

I verified empirically that $\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}\ge \sin(\frac{\theta}{n})$, which would imply $\beta\ge\frac{\theta}{n}$ too, but I'll leave the proof of that as an exercise, if true.

The example in my other answer led me to conjecture that the best possible result should be $$\sin(\beta)\ge \sin(\theta)\sqrt{\frac{(n-1)\tan(\theta)^2+n}{n((n-1)\tan(\theta)^2+n^2)}}$$

which is not much stonger than the claim, but probably much harder to prove.

deleted 1 character in body
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\}))$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i)$$

CLAIM. If $\theta_i\ge \theta>0$ for every $i$, then there is at least one $i$ such that $\displaystyle \beta_i\ge \frac{\theta}{n}$.

PROOF. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $X$ being invertible implies

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) This implies

$$\displaystyle |c_{ij}|\le \frac{1}{\sin(\theta)^2}$$

and therefore if $\beta=\max\{\beta_i\}$ $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \frac{n^2\sin(\beta)^2}{\sin(\theta)^2}$$

which implies $\sin(\beta)\ge \sin(\theta)/n$, and also $\beta\ge \theta/n$, by the monotonicity of the function $\sin(x)/x$ in $\blacksquare$$[0,\pi/2]$. $\quad\blacksquare$

The example in my other answer shows this result is best possible, in first order, as $\theta\rightarrow 0$.

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\}))$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i)$$

CLAIM. If $\theta_i\ge \theta>0$ for every $i$, then there is at least one $i$ such that $\displaystyle \beta_i\ge \frac{\theta}{n}$.

PROOF. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $X$ being invertible implies

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) This implies

$$\displaystyle |c_{ij}|\le \frac{1}{\sin(\theta)^2}$$

and therefore if $\beta=\max\{\beta_i\}$ $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \frac{n^2\sin(\beta)^2}{\sin(\theta)^2}$$

which implies $\sin(\beta)\ge \sin(\theta)/n$ and also $\beta\ge \theta/n$, by the monotonicity of the function $\sin(x)/x$ $\blacksquare$

The example in my other answer shows this result is best possible, in first order, as $\theta\rightarrow 0$.

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\}))$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i)$$

CLAIM. If $\theta_i\ge \theta>0$ for every $i$, then there is at least one $i$ such that $\displaystyle \beta_i\ge \frac{\theta}{n}$.

PROOF. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $X$ being invertible implies

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) This implies

$$\displaystyle |c_{ij}|\le \frac{1}{\sin(\theta)^2}$$

and therefore if $\beta=\max\{\beta_i\}$ $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \frac{n^2\sin(\beta)^2}{\sin(\theta)^2}$$

which implies $\sin(\beta)\ge \sin(\theta)/n$, and $\beta\ge \theta/n$ by monotonicity of $\sin(x)/x$ in $[0,\pi/2]$. $\quad\blacksquare$

The example in my other answer shows this result is best possible, in first order, as $\theta\rightarrow 0$.

added 138 characters in body
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\}))$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i)$$

Claim.CLAIM. If $\theta_i\ge \theta>0$ for every $i$, then there is at least one $i$ such that $\displaystyle \beta_i\ge \frac{\theta}{n}$.

Proof.PROOF. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $X$ being invertible implies

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) This implies

$$\displaystyle |c_{ij}|\le \frac{1}{\sin(\theta)^2}$$

and therefore if $\beta=\max\{\beta_i\}$ $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \frac{n^2\sin(\beta)^2}{\sin(\theta)^2}$$

which implies $\sin(\beta)\ge \sin(\theta)/n$ and also $\beta\ge \theta/n$, by the monotonicity of the function $\sin(x)/x$ $\blacksquare$

The example in my other answer shows this result is best possible, in first order, as $\theta\rightarrow 0$.

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\}))$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i)$$

Claim. If $\theta_i\ge \theta>0$ for every $i$, then there is at least one $i$ such that $\displaystyle \beta_i\ge \frac{\theta}{n}$.

Proof. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $X$ being invertible implies

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here, but a standard linear algebra text reference would be welcome.) This implies

$$\displaystyle |c_{ij}|\le \frac{1}{\sin(\theta)^2}$$

and therefore if $\beta=\max\{\beta_i\}$ $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \frac{n^2\sin(\beta)^2}{\sin(\theta)^2}$$

which implies $\sin(\beta)\ge \sin(\theta)/n$ and also $\beta\ge \theta/n$, by the monotonicity of the function $\sin(x)/x$ $\blacksquare$

The example in my other answer shows this result is best possible, in first order, as $\theta\rightarrow 0$.

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\}))$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i)$$

CLAIM. If $\theta_i\ge \theta>0$ for every $i$, then there is at least one $i$ such that $\displaystyle \beta_i\ge \frac{\theta}{n}$.

PROOF. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $X$ being invertible implies

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) This implies

$$\displaystyle |c_{ij}|\le \frac{1}{\sin(\theta)^2}$$

and therefore if $\beta=\max\{\beta_i\}$ $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \frac{n^2\sin(\beta)^2}{\sin(\theta)^2}$$

which implies $\sin(\beta)\ge \sin(\theta)/n$ and also $\beta\ge \theta/n$, by the monotonicity of the function $\sin(x)/x$ $\blacksquare$

The example in my other answer shows this result is best possible, in first order, as $\theta\rightarrow 0$.

shortened proof and fixed typo
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43
Loading
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43
Loading