About A Positive Semidefinite Kronecker Square
For integers n≥2, define a matrix An∈M2n(R) in the following way:
[An]ij={(n−1)2i=j1−ni,j adjacent1otherwise
where ``adjacent" means that either i≡j mod n, or ⌈i/n⌉=⌈j/n⌉. (The motivation of the name comes from listing the numbers 1,2,…,n2 in order starting from the top left in a n×n square. Then i,j are ``adjacent'' if they exist in the same row or column in this square.) We want to solve the problem of finding all the eigenvalues of An, and their corresponding multiplicities. This question was asked as MSE#3756186, which I was able to provide an answer. I found the problem interesting, so I'm recording it here.
After testing some cases using Mathematica, it was not so difficult to come up with a conjecture regarding the specific form of An. In particular, we find that An=(Jn−nIn)⊗2, where Jn is the n×n matrix of all 1s, In is the identity matrix and A⊗2 denotes the Kronecker square, i.e. the Kronecker product A⊗A. It is not difficult to prove this conjecture using some tedious arguments considering each entry.
We first derive the eigenvalues of Jn−nIn.
Lemma. The eigenvalues of Jn−nIn are 0 and −n, with multiplicities 1 and n−1 respectively.
Proof. By inspection, λ=−n makes det(Jn−nIn−λIn)=0 since n≥2. The (geometric) multiplicity of this eigenvalue is exactly dimker(Jn−nIn−λIn)=dimker(Jn)=n−dimim(Jn)=n−1. On the other hand, λ=0 is also an eigenvalue since we may compute that det(J−nIn)=0, as the sum of the bottom n−1 rows is the row vector [n−1,−1,…,−1], which is exactly −1 times the top row, so the rows are linearly dependent. Thus, the multiplicity of λ=0 is 1.
It follows from the above argument that the geometric multiplicities of both eigenvalues are the same as their algebraic multiplicities, since the geometric multiplicities sum to n. (A consequence of this is that the matrix is diagonalisable.) In the rest of this entry we shall base our arguments on geometric multiplicities, but the same logic applied here will be able to demonstrate that the algebraic multiplicities are actually the same thing.
From here, we invoke a well-known result regarding Kronecker products.
Theorem. Let K be a field, and let A∈Mn(K),B∈Mm(K) for m,n∈Z>0. Suppose λ is an eigenvalue of A with eigenvector x, and μ is an eigenvalue of B with eigenvector y. Then λμ is an eigenvalue of A⊗B with eigenvector x⊗y. ◻
Now we get to the claim.
Theorem. The eigenvalues of An are n2 and 0, with multiplicities (n−1)2 and 2n−1 respectively. Hence, An is positive semidefinite.
Proof. Invoking the Lemma, choose a basis {x1,x2,…,xn−1} of the eigenspace corresponding to the eigenvalue −n of (Jn−nIn). Via the Theorem above, for any 1≤i,j≤n−1 we have that xi⊗xj is an eigenvector for An=(Jn−nIn)⊗2 corresponding to eigenvalue n2. We have thus found (n−1)2 linearly independent eigenvectors for n2, so its multiplicity is at least (n−1)2. On the other hand, if y is an eigenvector corresponding to the eigenvalue 0 for (Jn−nIn), then {x1⊗y,…,xn−1⊗y,y⊗x1,…,y⊗xn−1,y⊗y} is a set of 2n−1 linearly independent eigenvectors for 0, so its multiplicity is at least 2n−1. But (n−1)2+(2n−1)=n2, so these are exactly their multiplicities.
We note that the linear independence of the two sets described in the proof above are nontrivial and need to be proven starting from the linear independence of {x1,…,xn−1,y}. This is however a standard result, and a proof can be found by a quick Google search. (Yes I’m cheating a bit… Sorry :P)
