Skip to main content
added 8 characters in body
Source Link
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

$\newcommand{\1}{\mathbf 1}\newcommand{\ep}{\varepsilon}\newcommand{\tr}{\operatorname{tr}}$The min-max value is $\sqrt n$.

Indeed, take any real $n\times n$ matrix $H$ with $|\det H|=1$. By the singular value decomposition,
\begin{equation} H=U^TDV, \end{equation} where $U$ and $V$ are some orthogonal matrices and $D$ is the diagonal matrix with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$. Then \begin{equation} \max_{\|x\|_2\le1}\|Hx\|_1=\max_{\|z\|_2\le1}\|U^TDz\|_1. \end{equation} So,
\begin{equation} \begin{aligned} &\min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1 \\ &=\min_{U,D}\max_{\|z\|_2\le1}\,\max_{\ep\in\{-1,1\}^n}\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\max_{\|z\|_2\le1}\,\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|_2, \end{aligned} \end{equation}\begin{equation} \begin{aligned} &\min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1 \\ &=\min_{U,D}\max_{\|z\|_2\le1}\,\max_{\ep\in\{-1,1\}^n}\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\max_{\|z\|_2\le1}\,\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|_2, \end{aligned} \end{equation} where (i) $\min_{U,D}$ denotes the minimum over all orthogonal matrices $U$ and all diagonal matrices $D$ with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$; (ii) the $e_i$'s are the standard basis vectors; (iii) $\ep:=(\ep_1,\dots,\ep_n)\in\{-1,1\}^n$ and $D_\ep$ is the diagonal matrix with diagonal entries $\ep_1,\dots,\ep_n$; and (iv) $\1:=\sum_{i=1}^n e_i$.

Now the crucial point: considering $\ep$ as a random point uniformly distributed on $\{-1,1\}^n$, we get the expected value of $E\|DUD_\ep\1\|_2^2$: \begin{equation} E\|DUD_\ep\1\|_2^2=\1^T ED_\ep U^T D^2 U D_\ep \1 =\tr U^T D^2 U=\tr D^2=\sum_{i=1}^n d_i^2\ge n, \end{equation} since $d_1\cdots d_n=1$. Hence, \begin{equation} \max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|\ge E\|DUD_\ep\1\|_2\ge\sqrt n. \end{equation} So, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1\ge\sqrt n. \end{equation}\begin{equation} \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1\ge\sqrt n. \end{equation} On the other hand, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1\le \max_{\|x\|_2\le1}\|x\|_1=\sqrt n. \end{equation}\begin{equation} \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1\le \max_{\|x\|_2\le1}\|x\|_1=\sqrt n. \end{equation}

Thus, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1=\sqrt n, \end{equation}\begin{equation} \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1=\sqrt n, \end{equation} as claimed.

$\newcommand{\1}{\mathbf 1}\newcommand{\ep}{\varepsilon}\newcommand{\tr}{\operatorname{tr}}$The min-max value is $\sqrt n$.

Indeed, take any real $n\times n$ matrix $H$ with $|\det H|=1$. By the singular value decomposition,
\begin{equation} H=U^TDV, \end{equation} where $U$ and $V$ are some orthogonal matrices and $D$ is the diagonal matrix with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$. Then \begin{equation} \max_{\|x\|_2\le1}\|Hx\|_1=\max_{\|z\|_2\le1}\|U^TDz\|_1. \end{equation} So,
\begin{equation} \begin{aligned} &\min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1 \\ &=\min_{U,D}\max_{\|z\|_2\le1}\,\max_{\ep\in\{-1,1\}^n}\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\max_{\|z\|_2\le1}\,\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|_2, \end{aligned} \end{equation} where (i) $\min_{U,D}$ denotes the minimum over all orthogonal matrices $U$ and all diagonal matrices $D$ with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$; (ii) the $e_i$'s are the standard basis vectors; (iii) $\ep:=(\ep_1,\dots,\ep_n)\in\{-1,1\}^n$ and $D_\ep$ is the diagonal matrix with diagonal entries $\ep_1,\dots,\ep_n$; and (iv) $\1:=\sum_{i=1}^n e_i$.

Now the crucial point: considering $\ep$ as a random point uniformly distributed on $\{-1,1\}^n$, we get the expected value of $E\|DUD_\ep\1\|_2^2$: \begin{equation} E\|DUD_\ep\1\|_2^2=\1^T ED_\ep U^T D^2 U D_\ep \1 =\tr U^T D^2 U=\tr D^2=\sum_{i=1}^n d_i^2\ge n, \end{equation} since $d_1\cdots d_n=1$. Hence, \begin{equation} \max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|\ge E\|DUD_\ep\1\|_2\ge\sqrt n. \end{equation} So, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1\ge\sqrt n. \end{equation} On the other hand, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1\le \max_{\|x\|_2\le1}\|x\|_1=\sqrt n. \end{equation}

Thus, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1=\sqrt n, \end{equation} as claimed.

$\newcommand{\1}{\mathbf 1}\newcommand{\ep}{\varepsilon}\newcommand{\tr}{\operatorname{tr}}$The min-max value is $\sqrt n$.

Indeed, take any real $n\times n$ matrix $H$ with $|\det H|=1$. By the singular value decomposition,
\begin{equation} H=U^TDV, \end{equation} where $U$ and $V$ are some orthogonal matrices and $D$ is the diagonal matrix with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$. Then \begin{equation} \max_{\|x\|_2\le1}\|Hx\|_1=\max_{\|z\|_2\le1}\|U^TDz\|_1. \end{equation} So,
\begin{equation} \begin{aligned} &\min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1 \\ &=\min_{U,D}\max_{\|z\|_2\le1}\,\max_{\ep\in\{-1,1\}^n}\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\max_{\|z\|_2\le1}\,\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|_2, \end{aligned} \end{equation} where (i) $\min_{U,D}$ denotes the minimum over all orthogonal matrices $U$ and all diagonal matrices $D$ with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$; (ii) the $e_i$'s are the standard basis vectors; (iii) $\ep:=(\ep_1,\dots,\ep_n)\in\{-1,1\}^n$ and $D_\ep$ is the diagonal matrix with diagonal entries $\ep_1,\dots,\ep_n$; and (iv) $\1:=\sum_{i=1}^n e_i$.

Now the crucial point: considering $\ep$ as a random point uniformly distributed on $\{-1,1\}^n$, we get the expected value of $E\|DUD_\ep\1\|_2^2$: \begin{equation} E\|DUD_\ep\1\|_2^2=\1^T ED_\ep U^T D^2 U D_\ep \1 =\tr U^T D^2 U=\tr D^2=\sum_{i=1}^n d_i^2\ge n, \end{equation} since $d_1\cdots d_n=1$. Hence, \begin{equation} \max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|\ge E\|DUD_\ep\1\|_2\ge\sqrt n. \end{equation} So, \begin{equation} \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1\ge\sqrt n. \end{equation} On the other hand, \begin{equation} \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1\le \max_{\|x\|_2\le1}\|x\|_1=\sqrt n. \end{equation}

Thus, \begin{equation} \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1=\sqrt n, \end{equation} as claimed.

added 2013 characters in body
Source Link
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

It is not hard to see that the$\newcommand{\1}{\mathbf 1}\newcommand{\ep}{\varepsilon}\newcommand{\tr}{\operatorname{tr}}$The min-max value is $\sqrt n$.

Indeed, take any real $n\times n$ matrix $H$ with $|\det H|=1$. By the singular value decomposition,
\begin{equation} H=U^TDV, \end{equation} where $U$ and $V$ are some orthogonal matrices and $D$ is the diagonal matrix with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$. Then \begin{equation} \max_{\|x\|_2\le1}\|Hx\|_1=\max_{\|z\|_2\le1}\|U^TDz\|_1. \end{equation} So,
\begin{equation} \begin{aligned} &\min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1 \\ &=\min_{U,D}\max_{\|z\|_2\le1}\,\max_{\ep\in\{-1,1\}^n}\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\max_{\|z\|_2\le1}\,\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|_2, \end{aligned} \end{equation} where (i) $\min_{U,D}$ denotes the minimum over all orthogonal matrices $U$ and all diagonal matrices $D$ with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$; (ii) the $e_i$'s are the standard basis vectors; (iii) $\ep:=(\ep_1,\dots,\ep_n)\in\{-1,1\}^n$ and $D_\ep$ is the diagonal matrix with diagonal entries $\ep_1,\dots,\ep_n$; and (iv) $\1:=\sum_{i=1}^n e_i$.

Now the crucial point: considering $\ep$ as a random point uniformly distributed on $\{-1,1\}^n$, we get the expected value of $E\|DUD_\ep\1\|_2^2$: \begin{equation} E\|DUD_\ep\1\|_2^2=\1^T ED_\ep U^T D^2 U D_\ep \1 =\tr U^T D^2 U=\tr D^2=\sum_{i=1}^n d_i^2\ge n, \end{equation} since $d_1\cdots d_n=1$. Hence, \begin{equation} \max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|\ge E\|DUD_\ep\1\|_2\ge\sqrt n. \end{equation} So, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1\ge\sqrt n. \end{equation} On the other hand, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1\le \max_{\|x\|_2\le1}\|x\|_1=\sqrt n. \end{equation}

Thus, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1=\sqrt n, \end{equation} as claimed.

It is not hard to see that the min-max value is $\sqrt n$.

$\newcommand{\1}{\mathbf 1}\newcommand{\ep}{\varepsilon}\newcommand{\tr}{\operatorname{tr}}$The min-max value is $\sqrt n$.

Indeed, take any real $n\times n$ matrix $H$ with $|\det H|=1$. By the singular value decomposition,
\begin{equation} H=U^TDV, \end{equation} where $U$ and $V$ are some orthogonal matrices and $D$ is the diagonal matrix with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$. Then \begin{equation} \max_{\|x\|_2\le1}\|Hx\|_1=\max_{\|z\|_2\le1}\|U^TDz\|_1. \end{equation} So,
\begin{equation} \begin{aligned} &\min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1 \\ &=\min_{U,D}\max_{\|z\|_2\le1}\,\max_{\ep\in\{-1,1\}^n}\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\max_{\|z\|_2\le1}\,\sum_{i=1}^n e_i^T D_\ep U^TDz \\ &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|_2, \end{aligned} \end{equation} where (i) $\min_{U,D}$ denotes the minimum over all orthogonal matrices $U$ and all diagonal matrices $D$ with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$; (ii) the $e_i$'s are the standard basis vectors; (iii) $\ep:=(\ep_1,\dots,\ep_n)\in\{-1,1\}^n$ and $D_\ep$ is the diagonal matrix with diagonal entries $\ep_1,\dots,\ep_n$; and (iv) $\1:=\sum_{i=1}^n e_i$.

Now the crucial point: considering $\ep$ as a random point uniformly distributed on $\{-1,1\}^n$, we get the expected value of $E\|DUD_\ep\1\|_2^2$: \begin{equation} E\|DUD_\ep\1\|_2^2=\1^T ED_\ep U^T D^2 U D_\ep \1 =\tr U^T D^2 U=\tr D^2=\sum_{i=1}^n d_i^2\ge n, \end{equation} since $d_1\cdots d_n=1$. Hence, \begin{equation} \max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|\ge E\|DUD_\ep\1\|_2\ge\sqrt n. \end{equation} So, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1\ge\sqrt n. \end{equation} On the other hand, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1\le \max_{\|x\|_2\le1}\|x\|_1=\sqrt n. \end{equation}

Thus, \begin{equation} \min_{H\colon\det H=1}\max_{\|x\|_2\le1}\|Hx\|_1=\sqrt n, \end{equation} as claimed.

Post Undeleted by Iosif Pinelis
Post Deleted by Iosif Pinelis
Post Undeleted by Iosif Pinelis
added 7 characters in body
Source Link
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

It is not hard to see that the min-max value is $\sqrt n$.

It is not hard that the min-max value is $\sqrt n$.

It is not hard to see that the min-max value is $\sqrt n$.

Post Deleted by Iosif Pinelis
added 6 characters in body
Source Link
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229
Loading
Post Undeleted by Iosif Pinelis
Post Deleted by Iosif Pinelis
Source Link
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229
Loading