1
$\begingroup$

This problem is motivated from one of my pattern mining research projects. Any helpful suggestions will be highly appreciated.

Consider an $n \times n$ correlation matrix A such that all the off-diagonal entries are between [-1,0]. (Note: A correlation matrix is a positive semi-definite symmetric matrix, with diagonal entries 1 and all off-diagonal entries between [-1,1]).

Let $\alpha_j = \frac{\sum_{i=1,i \neq j}^{n}|A_{ij}|}{n-1}$ denote the mean of magnitudes of off-diagonal entries in $j^{th}$ column. Let $\alpha_k = min_{j \in [1,n]}\alpha_j$.

Let $v_{min} = [v_1,v_2,...,v_n]^T$ be the unit eigenvector corresponding to the least eigenvalue $\lambda_{min}$ of A.

So far, I am observing empirically that $v_k \leq \frac{1}{\sqrt(n)}$.

I am wondering if this is indeed true in general, or otherwise, if there is any counterexample where this will break?

Note: For the cases with algebraic multiplicities (e.g. identity matrix), since the set of eigenvectors are not unique for such matrices and hence technically one might choose an appropriate eigenvector that would satisfy the above observation.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

As with Connection between weights in the last eigenvector (corresponding to least eigenvalue) and the corresponding column of a correlation matrix , this conjecture is also false. However, it is trickier to find a counterexample.

Here is the MATLAB output for a counterexample for n = 8. It is fairly close to the identity matrix, with eigenvalues ranging from about 0.99 to 1.01, with the smallest eigenvalue being only 9e-7 smaller than the 2nd largest eigenvalue.

disp(A), [eigenvec,eigenval] = eig(A), alpha = (sum(abs(A),1)-1)/7
   1.000000000000000  -0.000000013424584  -0.000000016728134  -0.000000031657700  -0.001541283052262  -0.009290809237230  -0.000000017416453  -0.000000025061704
  -0.000000013424584   1.000000000000000  -0.000779184667259  -0.000000023303448  -0.000000011369875  -0.000000050191099  -0.009659063867064  -0.000000023106687
  -0.000000016728134  -0.000779184667259   1.000000000000000  -0.000000022106295  -0.008662481225434  -0.000000019657000  -0.000000338414451  -0.000000053276645
  -0.000000031657700  -0.000000023303448  -0.000000022106295   1.000000000000000  -0.000000022992748  -0.000000037010141  -0.000000084752302  -0.009999292455459
  -0.001541283052262  -0.000000011369875  -0.008662481225434  -0.000000022992748   1.000000000000000  -0.000000050183901  -0.000000069002937  -0.000000023178821
  -0.009290809237230  -0.000000050191099  -0.000000019657000  -0.000000037010141  -0.000000050183901   1.000000000000000  -0.000004492558098  -0.000000130616618
  -0.000000017416453  -0.009659063867064  -0.000000338414451  -0.000000084752302  -0.000000069002937  -0.000004492558098   1.000000000000000  -0.000000731976591
  -0.000000025061704  -0.000000023106687  -0.000000053276645  -0.009999292455459  -0.000000023178821  -0.000000130616618  -0.000000731976591   1.000000000000000


eigenvec =

   0.393481914710150   0.189349681020513  -0.434978401237777  -0.346572242959196   0.346602815534381  -0.434841168090109   0.194019130411646   0.391326431246731
   0.388839803607549   0.186478415306430   0.543587869735760  -0.136166200284799  -0.136056769430420  -0.543694321928735  -0.190945953576501  -0.386555408885654
   0.331924445485950   0.159602182023258  -0.104005653327328   0.594588938172528  -0.594599826109975  -0.104018746142412   0.163448269453261   0.330024143230101
   0.306245310094574  -0.637348893611908  -0.000442596428886   0.000044151753147  -0.000014170805581  -0.000485014362688  -0.633723147483627   0.313679353671040
   0.348180985753816   0.167453314905593  -0.163972699085928   0.569072388198942   0.569070977229040   0.163957165900531  -0.171504332516948  -0.346210187579777
   0.365753875611087   0.176008958929152  -0.421457501097208  -0.397012014969461  -0.397043602012301   0.421322789791585  -0.180361063075395  -0.363749028068224
   0.375785499616817   0.180170396405265   0.547699729147779  -0.162322255159939   0.162236528576799   0.547808771349119   0.184485843964152   0.373564199185769
   0.306259570255542  -0.637342052739577  -0.000426534810891   0.000037456019517   0.000010816884866   0.000461122091144   0.633716797658318  -0.313692218132348


eigenval =

   0.989999973368053                   0                   0                   0                   0                   0                   0                   0
                   0   0.990000876849371                   0                   0                   0                   0                   0                   0
                   0                   0   0.990417008056811                   0                   0                   0                   0                   0
                   0                   0                   0   0.991887821278255                   0                   0                   0                   0
                   0                   0                   0                   0   1.008112357240175                   0                   0                   0
                   0                   0                   0                   0                   0   1.009583118785260                   0                   0
                   0                   0                   0                   0                   0                   0   1.009999208552940                   0
                   0                   0                   0                   0                   0                   0                   0   1.009999635869135


alpha =

   0.001547456654010   0.001491195704288   0.001348873725031   0.001428502039728   0.001457705857997   0.001327941350584   0.001380685426842   0.001428611381789

As can be seen, the smallest element of alpha is the 6th, with value 0.001327941350584. The first eigenvalue, 0.989999973368053, is the smallest. The corresponding eigenvector is the first column of eigenvec, whose 6th element has magnitude 0.365753875611087, which is greater than 1/sqrt(n) = 0.353553390593274. I am confident that the eigenvalue and eigenvector calculations are accurate enough to make this counterexample valid.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks Mark! While I agree that eigenvalue calculations might be accurate, note that the least two eigenvalues are fairly close similar to the 6th decimal places(like you mentioned). In such cases of algebraic multipliciities, I wonder whether the choice of eigenvectors will still be unique within the precision of MATLAB output. On a side note, I am curious as to how exactly did you manage to find such a case? Was it a random search or did you follow some heuristic approach? $\endgroup$
    – Saurabh Agrawal
    Commented Dec 18, 2017 at 6:53
  • $\begingroup$ I calculated the eigenvalues and eigenvectors in full octuple precision, and the results shown above are correct to all digits shown. So the results are correct. As for my method of finding this example, I generated a random matrix and solved a semidefinite optimization problem to produce a matrix meeting the required input properties, as part of which, i set the minimum allowable eigenvalue. In this case, I could "easily" generate counterexamples when I made the min eigenvalue close enough to 1. Had I known to look there, I could have simplified things and foregone semidefiinite optimization. $\endgroup$
    – Mark L. Stone
    Commented Dec 18, 2017 at 12:56
  • $\begingroup$ I see. Seems like such examples are likely to be found when the last two eigenvalues are very close. If it is not too difficult for you, could you please also run your method for alpha = sqrt((sum(abs(A.^2),1)-1)/7)? Basically, I am stating alpha to be root mean square of off-diagonal entries of column instead of simple mean. Or at the very least, compute new alphas for the above counterexample. Thanks again! $\endgroup$
    – Saurabh Agrawal
    Commented Dec 18, 2017 at 16:20
  • $\begingroup$ I can generate counterexamples at will with the "new" criterion in your comment. The smallest two eigenvalues don't have to be very close for this new criterion. For instance, with n = 8, I generated a counterexample whose two smallest eigenvalues are 0.2000 and 0.6252, and achieving "winning" eigenvector element of 0.3688 against 1//sqrt(n) = 0.3536. It appears easier to get counterexamples having large separation between smallest two eigenvalues with the new criterion than with the original criterion. $\endgroup$
    – Mark L. Stone
    Commented Dec 18, 2017 at 17:38
  • $\begingroup$ Here are the corresponding "new" alpha values, so as you can see, element 7 wins without being a close call. [0.3132 0.3164 0.3262 0.3418 0.3334 0.3354 0.2688 0.2757] $\endgroup$
    – Mark L. Stone
    Commented Dec 18, 2017 at 17:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .