Return to Answer

Here is a solution inspired by Losif Pinelis, but addresses the existence of non-singular matrices (see comment to last answer).

First consider part 1, and for this first consider the case where $diag(R)= 1_N$, the "all ones vector", and $|v_1| > |v_2| > ... > |v_N|$. Let $\{e_1,...,e_N\}$ be the natural basis, $q_i= (v_i/v_1 )e_1 + \sqrt{1-(v_i/v_1)^2} e_i$, $1\leq i\leq N$, $Q_0= [q_1, q_2, ..., q_N]$, $R_0= Q_0'Q_0$. Note that by construction $||q_i||= 1$, $Q_0$ is lower triangular with positive diagonal entries, and thus is non-singular. Also note, $e_i'Q_0e_1= v_i/v_1$, so $Q_0^{-T}v= v_1e_1$, and thus, $v'R^{-1}v= v'Q_0^{-1}Q_0^{-T}v= ||Q_0^{-T}v||^2= ||v_1e_1||^2= v_1^2= ||v||_\infty^2$. But given any non-singular $R$ with $R=R'$, and $diag(R)=1_N$, there exists a Cholesky factorization, $R= Q'Q$, and by the Cauchy-Schwartz Lemma, $v'R^{-1}v= ||Q^{-T}v||^2 >= (q_1'Q^{-T}v)^2=(e_1'Q^T Q^{-T}v)^2= v_1^2= ||v||_\infty^2$; so, $R_0$ is a global minimum; and $\min\{v'R^{-1}v\}= ||v||_\infty^2$.

Now consider the case where we still have $diag(R)= 1_N$, and $v$ sorted, but $v$'s entries are not distinct. The $Q_0$ as constructed above is singular, but since $v'R^{-1}v$ is a continuous function of $R$, it can be extended to $\inf\{v'R^{-1}v\}= ||v||_\infty^2$.

Finally, consider the more general case. Let $\Lambda= diag(r)^{-1/2}$, and $w= \Lambda v$. Also, for each $R$, let $G= \Lambda R \Lambda$, so $diag(G)= 1_N$. Then, $\inf\{v'R^{-1}v\}= \inf\{v'\Lambda \Lambda^{-1} R^{-1} \Lambda^{-1} \Lambda v\}= \inf\{w'G^{-1}w\}= ||w||_\infty^2=||diag(r)^{-1/2}v||_\infty^2$. This proves $\inf\{v'*R^{-1}v\}= ||diag(r)^{-1/2}v||_\infty^2$.

Now consider the second problem. Let $w= diag(r)^{1/2}sign(v)$, and $R_0= ww'$. So, $v'R_0 v= \sum{v_i v_j R_0[i,j]}= \sum{v_i v_j \sqrt{r_i} sign(v_i) \sqrt{r_j} sign(v_j)}= ||diag(r)^{1/2}v||_1^2$. But given $R>0$, $|\sum{v_i v_j R[i,j]}|\leq \sum{|v_i v_j R_{i,j}|}\leq\sum{|v_i v_j \sqrt{r_i} \sqrt{r_j}|}= ||diag(r)^{1/2}v||_1^2$; so, $R_0$ is a global maximizer. This proves $\sup{v'Rv}= ||diag(r)^{1/2}v||_1^2$.

Juxtaposing our solutions for parts 1 and 2, we have the following.

$\inf\{v'R^{-1}v:R>0, diag(R)=r\}= ||diag(r)^{-1/2}v||_\infty^2$

$\sup\{v'Rv:R>0, diag(R)=r\}= ||diag(r)^{1/2}v||_1^2$

which agrees with Losif Pinelis' answer, and when expressed this way, exhibits a shocking duality. Is this a coincidence, or a hint at something deeper?

Here is a solution inspired by Losif Pinelis, but addresses the existence of non-singular matrices (see comment to last answer).

First consider part 1, and for this first consider the case where $diag(R)= 1_N$, the "all ones vector", and $|v_1| > |v_2| > ... > |v_N|$. Let $\{e_1,...,e_N\}$ be the natural basis, $q_i= (v_i/v_1 )e_1 + \sqrt{1-(v_i/v_1)^2} e_i$, $1\leq i\leq N$, $Q_0= [q_1, q_2, ..., q_N]$, $R_0= Q_0'Q_0$. Note that by construction $||q_i||= 1$, $Q_0$ is upper-triangular with positive diagonal entries, and thus is non-singular. Also note, $e_i'Q_0e_1= v_i/v_1$, so $Q_0^{-T}v= v_1e_1$, and thus, $v'R_0^{-1}v= v'Q_0^{-1}Q_0^{-T}v= ||Q_0^{-T}v||^2= ||v_1e_1||^2= v_1^2= ||v||_\infty^2$. But given any non-singular $R$ with $R=R'$, and $diag(R)=1_N$, there exists a Cholesky factorization, $R= Q'Q$, and by the Cauchy-Schwartz Lemma, $v'R^{-1}v= ||Q^{-T}v||^2 >= (q_1'Q^{-T}v)^2=(e_1'Q^T Q^{-T}v)^2= v_1^2= ||v||_\infty^2$; so, $R_0$ is a global minimum; and $\min\{v'R^{-1}v\}= ||v||_\infty^2$. Note, that in the above argument, the only critical property of $v$ is that it's elements are distinct, thus $\min\{v'R^{-1}v\}= ||v||_\infty^2$ holds for any distinct $v$, regardless of it's ordering.

Now consider the case where we still have $diag(R)= 1_N$, and $v$ sorted, but $v$'s entries are not distinct. The $Q_0$ as constructed above is singular, but since $v'R^{-1}v$ is a continuous function of $R$ on a bounded set, it can be extended to $\inf\{v'R^{-1}v\}= ||v||_\infty^2$, where R is taken over the set of positive semi-definite matrices (not just positive definite matrices).

Finally, consider the more general case. Let $\Lambda= diag(r)^{-1/2}$, and $w= \Lambda v$. Also, for each $R$, let $G= \Lambda R \Lambda$, so $diag(G)= 1_N$. Then, $\inf\{v'R^{-1}v\}= \inf\{v'\Lambda \Lambda^{-1} R^{-1} \Lambda^{-1} \Lambda v\}= \inf\{w'G^{-1}w\}= ||w||_\infty^2=||diag(r)^{-1/2}v||_\infty^2$. This proves $\inf\{v'*R^{-1}v\}= ||diag(r)^{-1/2}v||_\infty^2$.

Now consider the second problem. Let $w= diag(r)^{1/2}sign(v)$, and $R_0= ww'$. So, $v'R_0 v= \sum{v_i v_j R_0[i,j]}= \sum{v_i v_j \sqrt{r_i} sign(v_i) \sqrt{r_j} sign(v_j)}= ||diag(r)^{1/2}v||_1^2$. But given $R>0$, $|\sum{v_i v_j R[i,j]}|\leq \sum{|v_i v_j R_{i,j}|}\leq\sum{|v_i v_j \sqrt{r_i} \sqrt{r_j}|}= ||diag(r)^{1/2}v||_1^2$; so, $R_0$ is a global maximizer. This proves $\sup{v'Rv}= ||diag(r)^{1/2}v||_1^2$.

Juxtaposing our solutions for parts 1 and 2, we have the following.

$\inf\{v'R^{-1}v:R>0, diag(R)=r\}= ||diag(r)^{-1/2}v||_\infty^2$

$\sup\{v'Rv:R>0, diag(R)=r\}= ||diag(r)^{1/2}v||_1^2$

which agrees with Losif Pinelis' answer, and when expressed this way, exhibits a shocking duality. Is this a coincidence, or a hint at something deeper?

Here is a solution inspired by Losif Pinelis, but addresses the existence of non-singular matrices (see comment to last answer).

First consider part 1, and for this first consider the case where $diag(R)= 1_N$, the "all ones vector", and $|v_1| > |v_2| > ... > |v_N|$. Let $\{e_1,...,e_N\}$ be the natural basis, $q_i= (v_i/v_1 )e_1 + \sqrt{1-(v_i/v_1)^2} e_i$, $1\leq i\leq N$, $Q_0= [q_1, q_2, ..., q_N]$, $R_0= Q_0'Q_0$. Note that by construction $||q_i||= 1$, $Q_0$ is lower triangular with positive diagonal entries, and thus is non-singular. Also note, $e_i'Q_0e_1= v_i/v_1$, so $Q_0^{-T}v= v_1e_1$, and thus, $v'R^{-1}v= v'Q_0^{-1}Q_0^{-T}v= ||Q_0^{-T}v||^2= ||v_1e_1||^2= v_1^2= ||v||_\infty^2$. But given any non-singular $R$ with $R=R'$, and $diag(R)=1_N$, there exists a Cholesky factorization, $R= Q'Q$, and by the Cauchy-Schwartz Lemma, $v'R^{-1}v= ||Q^{-T}v||^2 >= (q_1'Q^{-T}v)^2=(e_1'Q^T Q^{-T}v)^2= v_1^2= ||v||_\infty^2$; so, $R_0$ is a global minimum; and $min\{v'R^{-1}v\}= ||v||_\infty^2$.

Now consider the case where $diag(R)= 1_N$, and $v$ sorted, by $v$'s entries are not distinct. The $Q_0$ as constructed above is singular, but since $v'R^{-1}v$ is a continuous function of $R$, it can be extended to $inf{v'R^{-1}v}= ||v||_\infty^2$.

Finally, consider the more general case. Let $\Lambda= diag(r)^{-1/2}$, and $w= \Lambda v$. Also, for each $R$, let $G= \Lambda R \Lambda$, so $diag(G)= 1_N$. Then, $inf{v'R^{-1}v}= inf{v'\Lambda \Lambda^{-1} R^{-1} \Lambda^{-1} \Lamba v}= inf{w'G^{-1}w}= ||w||\infty^2= = ||diag(r)^{-1/2}v||\Inf^2. This proves inf{v'*inv(R)v}= ||diag(r)^{-1/2}v||_\infty^2.

Now consider the second problem. Let $w= diag(r)^(1/2)sign(v)$, and $R_0= ww'$. So, $v'R_0 v= sum{v_i v_j R[i,j]}= sum{v_i v_j \sqrt(r_i) sign(v_i) \sqrt(r_j) sign(v_j)}= ||diag(r)^(1/2)v||_1^2$. But $|sum{v_i v_j R[i,j]}|<= sum{|v_i v_j R[i,j]|}<=sum{|v_i v_j \sqrt(r_i) \sqrt(r_j)|}= ||diag(r)^(1/2)v||_1^2$; so, $R_0$ is a global maximizer. This proves $sup{v'Rv}= ||diag(r)^(1/2)v||_1^2$.

Juxtaposing our solutions for parts 1 and 2, we have the following. inf{v'*inv(R)v}= ||diag(r)^(-1/2)v||_\Inf^2 sup{v'Rv}= ||diag(r)^(1/2)v||_1^2 which exhibits a shocking duality. Is this a coincidence, or a hint at something deeper?

Here is a solution inspired by Losif Pinelis, but addresses the existence of non-singular matrices (see comment to last answer).

First consider part 1, and for this first consider the case where $diag(R)= 1_N$, the "all ones vector", and $|v_1| > |v_2| > ... > |v_N|$. Let $\{e_1,...,e_N\}$ be the natural basis, $q_i= (v_i/v_1 )e_1 + \sqrt{1-(v_i/v_1)^2} e_i$, $1\leq i\leq N$, $Q_0= [q_1, q_2, ..., q_N]$, $R_0= Q_0'Q_0$. Note that by construction $||q_i||= 1$, $Q_0$ is lower triangular with positive diagonal entries, and thus is non-singular. Also note, $e_i'Q_0e_1= v_i/v_1$, so $Q_0^{-T}v= v_1e_1$, and thus, $v'R^{-1}v= v'Q_0^{-1}Q_0^{-T}v= ||Q_0^{-T}v||^2= ||v_1e_1||^2= v_1^2= ||v||_\infty^2$. But given any non-singular $R$ with $R=R'$, and $diag(R)=1_N$, there exists a Cholesky factorization, $R= Q'Q$, and by the Cauchy-Schwartz Lemma, $v'R^{-1}v= ||Q^{-T}v||^2 >= (q_1'Q^{-T}v)^2=(e_1'Q^T Q^{-T}v)^2= v_1^2= ||v||_\infty^2$; so, $R_0$ is a global minimum; and $\min\{v'R^{-1}v\}= ||v||_\infty^2$.

Now consider the case where we still have $diag(R)= 1_N$, and $v$ sorted, but $v$'s entries are not distinct. The $Q_0$ as constructed above is singular, but since $v'R^{-1}v$ is a continuous function of $R$, it can be extended to $\inf\{v'R^{-1}v\}= ||v||_\infty^2$.

Finally, consider the more general case. Let $\Lambda= diag(r)^{-1/2}$, and $w= \Lambda v$. Also, for each $R$, let $G= \Lambda R \Lambda$, so $diag(G)= 1_N$. Then, $\inf\{v'R^{-1}v\}= \inf\{v'\Lambda \Lambda^{-1} R^{-1} \Lambda^{-1} \Lambda v\}= \inf\{w'G^{-1}w\}= ||w||_\infty^2=||diag(r)^{-1/2}v||_\infty^2$. This proves $\inf\{v'*R^{-1}v\}= ||diag(r)^{-1/2}v||_\infty^2$.

Now consider the second problem. Let $w= diag(r)^{1/2}sign(v)$, and $R_0= ww'$. So, $v'R_0 v= \sum{v_i v_j R_0[i,j]}= \sum{v_i v_j \sqrt{r_i} sign(v_i) \sqrt{r_j} sign(v_j)}= ||diag(r)^{1/2}v||_1^2$. But given $R>0$, $|\sum{v_i v_j R[i,j]}|\leq \sum{|v_i v_j R_{i,j}|}\leq\sum{|v_i v_j \sqrt{r_i} \sqrt{r_j}|}= ||diag(r)^{1/2}v||_1^2$; so, $R_0$ is a global maximizer. This proves $\sup{v'Rv}= ||diag(r)^{1/2}v||_1^2$.

Juxtaposing our solutions for parts 1 and 2, we have the following.

$\inf\{v'R^{-1}v:R>0, diag(R)=r\}= ||diag(r)^{-1/2}v||_\infty^2$

$\sup\{v'Rv:R>0, diag(R)=r\}= ||diag(r)^{1/2}v||_1^2$

which agrees with Losif Pinelis' answer, and when expressed this way, exhibits a shocking duality. Is this a coincidence, or a hint at something deeper?

Here is a solution inspired by Losif Pinelis, but addresses the existence of non-singular matrices (see comment to last answer).

First consider part 1, and for this first consider the case where $diag(R)= 1_N$, the "all ones vector", and $|v_1| > |v_2| > ... > |v_N|$. Let $\{e_1,...,e_N\}$ be the natural basis, $q_i= (v_i/v_1 )e_1 + \sqrt{1-(v_i/v_1)^2} e_i$, $1\leq i\leq N$, $Q_0= [q_1, q_2, ..., q_N]$, $R_0= Q_0'Q_0$. Note that by construction $||q_i||= 1$, $Q_0$ is lower triangular with positive diagonal entries, and thus is non-singular. Also note, $e_i'Q_0e_1= v_i/v_1$, so $Q_0^{-T}v= v_1e_1$, and thus, $v'R^{-1}v= v'Q_0^{-1}Q_0^{-T}v= ||Q_0^{-T}v||^2= ||v_1e_1||^2= v_1^2= ||v||_\infty^2$. But given any non-singular $R$ with $R=R'$, and $diag(R)=1_N$, there exists a Cholesky factorization, $R= Q'Q$, and by the Cauchy-Schwartz Lemma, $v'R^{-1}v= ||Q^{-T}v||^2 >= (q_1'Q^{-T}v)^2=(e_1'Q^T Q^{-T}v)^2= v_1^2= ||v||_\infty^2$; so, $R_0$ is a global minimum; and $min\{v'R^{-1}v\}= ||v||_\infty^2$.

Now consider the case where $diag(R)= 1_N$, and $v$ sorted, by $v$'s entries are not distinct. The $Q_0$ as constructed above is singular, but since $v'R^{-1}v$ is a continuous function of $R$, it can be extended to $inf{v'R^{-1}v}= ||v||_\infty^2$.

Finally, consider the more general case. Let $\Lambda= diag(r)^{-1/2}$, and $w= \Lambda v$. Also, for each $R$, let $G= \Lambda R \Lambda$, so $diag(G)= 1_N$. Then, $inf{v'R^{-1}v}= inf{v'\Lambda \Lambda^{-1} R^{-1} \Lambda^{-1} \Lamba v}= inf{w'G^{-1}w}= ||w||\infty^2= = ||diag(r)^{-1/2}v||\Inf^2. This proves inf{v'*inv(R)v}= ||diag(r)^{-1/2}v||_\infty^2.

Now consider the second problem. Let w= diag(r)^(1/2)sign(v), and Ro= ww'. So, v'Ro v= sum{v_i v_j R[i,j]}= sum{v_i v_j \sqrt(r_i) sign(v_i) \sqrt(r_j) sign(v_j)}= ||diag(r)^(1/2)v||_1^2. But |sum{v_i v_j R[i,j]}|<= sum{|v_i v_j R[i,j]|}<=sum{|v_i v_j \sqrt(r_i) \sqrt(r_j)|}= ||diag(r)^(1/2)v||_1^2; so, Ro is a global maximizer. This proves sup{v'Rv}= ||diag(r)^(1/2)v||_1^2.

Juxtaposing our solutions for parts 1 and 2, we have the following. inf{v'*inv(R)v}= ||diag(r)^(-1/2)v||_\Inf^2 sup{v'Rv}= ||diag(r)^(1/2)v||_1^2 which exhibits a shocking duality. Is this a coincidence, or a hint at something deeper?

Here is a solution inspired by Losif Pinelis, but addresses the existence of non-singular matrices (see comment to last answer).

First consider part 1, and for this first consider the case where $diag(R)= 1_N$, the "all ones vector", and $|v_1| > |v_2| > ... > |v_N|$. Let $\{e_1,...,e_N\}$ be the natural basis, $q_i= (v_i/v_1 )e_1 + \sqrt{1-(v_i/v_1)^2} e_i$, $1\leq i\leq N$, $Q_0= [q_1, q_2, ..., q_N]$, $R_0= Q_0'Q_0$. Note that by construction $||q_i||= 1$, $Q_0$ is lower triangular with positive diagonal entries, and thus is non-singular. Also note, $e_i'Q_0e_1= v_i/v_1$, so $Q_0^{-T}v= v_1e_1$, and thus, $v'R^{-1}v= v'Q_0^{-1}Q_0^{-T}v= ||Q_0^{-T}v||^2= ||v_1e_1||^2= v_1^2= ||v||_\infty^2$. But given any non-singular $R$ with $R=R'$, and $diag(R)=1_N$, there exists a Cholesky factorization, $R= Q'Q$, and by the Cauchy-Schwartz Lemma, $v'R^{-1}v= ||Q^{-T}v||^2 >= (q_1'Q^{-T}v)^2=(e_1'Q^T Q^{-T}v)^2= v_1^2= ||v||_\infty^2$; so, $R_0$ is a global minimum; and $min\{v'R^{-1}v\}= ||v||_\infty^2$.

Now consider the case where $diag(R)= 1_N$, and $v$ sorted, by $v$'s entries are not distinct. The $Q_0$ as constructed above is singular, but since $v'R^{-1}v$ is a continuous function of $R$, it can be extended to $inf{v'R^{-1}v}= ||v||_\infty^2$.

Finally, consider the more general case. Let $\Lambda= diag(r)^{-1/2}$, and $w= \Lambda v$. Also, for each $R$, let $G= \Lambda R \Lambda$, so $diag(G)= 1_N$. Then, $inf{v'R^{-1}v}= inf{v'\Lambda \Lambda^{-1} R^{-1} \Lambda^{-1} \Lamba v}= inf{w'G^{-1}w}= ||w||\infty^2= = ||diag(r)^{-1/2}v||\Inf^2. This proves inf{v'*inv(R)v}= ||diag(r)^{-1/2}v||_\infty^2.

Now consider the second problem. Let $w= diag(r)^(1/2)sign(v)$, and $R_0= ww'$. So, $v'R_0 v= sum{v_i v_j R[i,j]}= sum{v_i v_j \sqrt(r_i) sign(v_i) \sqrt(r_j) sign(v_j)}= ||diag(r)^(1/2)v||_1^2$. But $|sum{v_i v_j R[i,j]}|<= sum{|v_i v_j R[i,j]|}<=sum{|v_i v_j \sqrt(r_i) \sqrt(r_j)|}= ||diag(r)^(1/2)v||_1^2$; so, $R_0$ is a global maximizer. This proves $sup{v'Rv}= ||diag(r)^(1/2)v||_1^2$.

Juxtaposing our solutions for parts 1 and 2, we have the following. inf{v'*inv(R)v}= ||diag(r)^(-1/2)v||_\Inf^2 sup{v'Rv}= ||diag(r)^(1/2)v||_1^2 which exhibits a shocking duality. Is this a coincidence, or a hint at something deeper?