1
$\begingroup$

Let $\mathbf{A}$ be any $n\times n$ symmetric positive matrix ($A_{ij}>0$). It is easy to show that the solution to the following optimization problem

\begin{align} \max_{\mathbf{x}}~~\mathbf{x^TAx}\,\,;s.t.~~\mathbf{x}\geq \mathbf{0},~~\|\mathbf{x}\|_2=1 \end{align}

is given by the so-called Perron vector of $\mathbf{A}$, which will the eigenvector corresponding to the largest eigenvalue (known as the Perron root). It will also turn out that the Perron vector has all its entries as positive. I need to see if Perron vector is still a solution if I replace the $2$-norm constraint with the $1$-norm constraint. I need to know if the Perron vector will be a solution to

\begin{align} \max_{\mathbf{x}}~~\mathbf{x^TAx}\,\,;s.t.~~\mathbf{x}\geq \mathbf{0},~~\|\mathbf{x}\|_1=1 \end{align}

If it is not, how badly does it miss out? Is there any research on this? This comes from an engineering problem I am working on.

$\endgroup$
  • 2
    $\begingroup$ In English, in such names as "Perron vector", the capital letter is used. $\endgroup$ – Alexandre Eremenko Sep 17 '19 at 12:12
  • $\begingroup$ Just consider the identity matrix. Every feasible vector (feasible means satisfies the constraints) is also optimal for the first problem but it may not even be feasible for the second one. $\endgroup$ – Pushpendre Sep 18 '19 at 2:30
  • $\begingroup$ @Pushpendre thanks!. In my case, the matrix is strictly positive ($A_{ij}>0$) and in fact, it is ok to assume that the matrix is positive definite. Examples pointed out in the answer as well as your comment are extremely sparse. I am wondering (and hoping) if that makes a difference $\endgroup$ – dineshdileep Sep 18 '19 at 3:07
  • $\begingroup$ Why is this convex? $\endgroup$ – Rodrigo de Azevedo Sep 18 '19 at 6:00
  • $\begingroup$ It doesn't require convexity. $\endgroup$ – dineshdileep Sep 18 '19 at 6:04
6
$\begingroup$

No. The Perron vector is in general very far from optimizing the quantity you're looking at. Here is an example: Let $A$ be the $n\times n$ tridiagonal matrix with $\frac 13$ on the diagonal and the off-diagonals as well as in the $(1,n)$ and $(n,1)$ entries. (I think of this as a Markov transition matrix on a ring of size $n$ with probability $\frac 13$ of staying still or moving left or right).

The Perron vector of norm 1 is the vector $x=(\frac 1n,\ldots,\frac 1n)^T$. This is an eigenvector with eigenvalue 1, so that $x^TAx=1/n$. On the other hand, if $y$ is the coordinate vector $(1,0,\ldots,0)^T$, then $y^TAy=\frac 13$ so the Perron vector is nowhere close to optimizing $x^TAx$ over the $\ell^1$ unit ball.

$\endgroup$
  • $\begingroup$ Thanks, this is insightful. But please note that the matrix I have is strictly positive ($A_{ij}>0$) whereas the matrix in your example is extremely sparse for larger $n$. Do you think this will make a difference? $\endgroup$ – dineshdileep Sep 17 '19 at 3:47
  • 1
    $\begingroup$ @dineshdileep: No, this doesn't make a difference. You can simply perturb the matrix to make all entries strictly positive, but if the perturbation is small enough, this won't change the phenomenon described in Anthony Quas' answer. $\endgroup$ – Jochen Glueck Sep 17 '19 at 6:26
  • 2
    $\begingroup$ The spirit of the answer is that $\ell^2$ looks very different from $\ell^1$ in the diagonal direction (by a factor of $\sqrt n$). Finding a matrix whose Perron vector is close to the diagonal direction means that the $\ell^1$ version of it is much smaller. This makes it easier to beat the value coming from the Perron vector. As an explicit perturbation along the lines suggested by @JochenGlueck, you could replace all of the 1/3 by 1/4; and replace the 0’s by $1/(4(n-3))$. The Perron vector is the same so $x^TAx=1/n$ and $y^TAy=1/4$. $\endgroup$ – Anthony Quas Sep 17 '19 at 23:36
  • $\begingroup$ @AnthonyQuas got it!... $\endgroup$ – dineshdileep Sep 18 '19 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.