4
$\begingroup$

In an attempt to formulate a answer to this (in)famous question

I'm trying to construct three $n\times n$ matrices $A,B,C$ that are (a) symmetric, (b) positive definite, (c) add to $I_n$ . Note that I've already decided to restrict attention to the reals and I have replaced Hermitian by symmetric (which IMO is difficult enough).

My unsuccessful tries are a wild mixture of two extremes:

  • Make a random square matrix $H$ and form $A = H^TH$ . Make another random square matrix $H$ and form $B = H^TH$ . In the same way, form $C = H^TH$ . Then $A,B,C$ are symmetric and positive definite. But in general $A+B+C \ne I$ .
  • Generate random numbers for $A_{ij} = A_{ji}$ , $B_{ij} = B_{ji}$ and form $C_{ij} = C_{ji} = I_{ij}-A_{ij}-B_{ij}$ . Then $A,B,C$ are symmetric and $A+B+C = I$ , but it cannot be guaranteed that these are positive definite matrices.
So the question is: how can the three requirements (a) , (b) , (c) be fulfilled at the same time, while keeping $A,B,C$ yet as random as possible? My plan is to do numerical experiments and eventually find a counter example. I have all the ingredients to do it, except this.

$\endgroup$
3
$\begingroup$

This is easy. Denote by $\operatorname{diag}(x)$ the diagonal matrix whose diagonal is the vector $x$. Assuming that $A$ is diagonal, every valid triple $(A,B,C)$ can be expressed as follows: \begin{align*} A&=\operatorname{diag}(a),\\ R&=(I-A)^{1/2},\\ B&=RU\operatorname{diag}(b)U^\ast R,\\ C&=I-A-B, \end{align*} where $a$ and $b$ are two vectors whose entries lie inside $(0,1)$ and $U$ is a unitary matrix. Note that $C=RU\left(I-\operatorname{diag}(b)\right)U^\ast R$. Hence it is positive definite.

So, to generate a random sample, all you need are random instances of $a,b$ and $U$. The unitary matrix $U$ can be obtained by performing a singular value decomposition on a random square matrix, or you may generate it using the method mentioned in Wikipedia.

$\endgroup$
  • 1
    $\begingroup$ You call this easy ? It may be my inexperience (surely is), but I cannot even imagine how to make a start with an algorithm that implements some of it. $\endgroup$ – Han de Bruijn Jan 6 '17 at 11:47
  • 1
    $\begingroup$ @HandeBruijn You don't implement everything, do you? If you want to do a numerical experiment, you should use either a numerical programming environment or any programming language with an appropriate numerical library. Using Matlab/Octave, for instance, we can implement the above algorithm with a few lines of code: n=2;tol=1e-6;for k=1:10000,A=diag(rand(n,1));R=sqrt(A);[U,S,V]=svd(rand(n,n)+i*rand(n,n));B=R*U*diag(rand(n,1))*U'*R;C=eye(n)-A-B;d=det(6*(A^3+B^3+C^3)+eye(n))-det(5*(A^2+B^2+C^2));if d<-tol,A,B,C,d,break;end;end $\endgroup$ – user1551 Jan 6 '17 at 12:55
  • $\begingroup$ Sounds as if you actually did it :-) If so, then my attempts shall be redundant. Right? $\endgroup$ – Han de Bruijn Jan 6 '17 at 13:03
  • 1
    $\begingroup$ @HandeBruijn Yes, I did it. See my comment dated Sep 12 '14 under that question. I had also used this algorithm to find a counterexample to the hypothesis that $6(A^3+B^3+C^3)+I\succeq5(A^2+B^2+C^2)$. As for redundancy, that's a good thing: more redundancy means a higher chance to get a counterexample, doesn't it? $\endgroup$ – user1551 Jan 6 '17 at 14:09
  • $\begingroup$ Yes, I've noticed that, soon after your comment with the program snippet in it. Meanwhile, I've managed to do experiments for numerous random $2\times 2$ and $3\times 3$ matrices, though with a lot more overhead involved than needed. The reason is that I don't have many advanced tools at my disposal (ever since being a pensionado, and with the advent of Windows 10, sic). So indeed I'm implementing a lot from scratch. Needless to say that the conjecture still stands. And no, after having read your profile, I'm not going to publish anything annoying and give you all possible credits instead. $\endgroup$ – Han de Bruijn Jan 6 '17 at 14:49

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.