4
$\begingroup$

It is needed to generate all 8th order(8 by 8) symmetric binary matrices(of 0's and 1's) such that the sum of the absolute eigenvalues is 8. Listing all the 8th order symmetric binary matrices and then finding the sum of the absolute eigen values is not a computationally feasible way. Can anybody help to generate the mentioned list of matrices only, which are supposed to be very less in number?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Sorry, but what is an "8th order symmetric matrix"; I'm assuming by binary you just mean all values are 0 or 1. Also at some level this feels like more of a math question than a Mathematica question, unless you can provide us with code that we can play with or optimize. Most of the work seems to be in designing a constructive approach mathematically, rather than computationally or algorithmically $\endgroup$
    – b3m2a1
    Commented Apr 4, 2021 at 5:30
  • 1
    $\begingroup$ There are $2^{36}$ (about 69 billion) symmetric binary $8\times8$ matrices, which isn't crazy-much. A fast algorithm could surely search through all of them, though you'd probably have to write it in a low-level language, not Mathematica. Start by implementing a fast selector based on LAPACK's ssyev function, then loop over all matrices. It's probably enough to look at matrices whose trace is even. $\endgroup$
    – Roman
    Commented Apr 4, 2021 at 16:28
  • 1
    $\begingroup$ Since applying the same permutation to both rows and columns doesn't change the eigenvalues, the search space is effectively reduced by a factor of 8! $\endgroup$
    – mikado
    Commented Apr 4, 2021 at 16:43
  • 1
    $\begingroup$ Modulo conjugation by permutation matrices, we may assume that the diagonal of $A$ consists of $r$ entries $1$, followed by $8-r$ entries $0$. As $A$ is symmetric, all its eigenvalues $\lambda_i$ are real. By looking at the effects on an eigenvector at its maximal component, we also see that $-7\le\lambda_i\le 8$ (and in fact $8$ can be replaced by the maximal column weight). We want $\sum |\lambda_i|=8$ and have $\sum \lambda_i = \operatorname{tr}A=r$. It follows that $\sum_{\lambda_i>0}\lambda_i =4+\frac r2$ and $\sum_{\lambda_i<0}\lambda_i=\frac r2-4$. (cont.) $\endgroup$
    – Hagen von Eitzen
    Commented Apr 4, 2021 at 21:34
  • 1
    $\begingroup$ (cont) Looking at the next coefficient of the characteristic polynomial, we conclude that $\left|\sum_{i<j} \lambda_i\lambda_j\right|$ is an integer $\le {8\choose 2}$, and more generally for the $k$th coefficient, $\le{8\choose k}\frac{k!}2$. (In particular, $|\det A|\le \frac{8!}2$). -- not sure if that helps $\endgroup$
    – Hagen von Eitzen
    Commented Apr 4, 2021 at 21:34

2 Answers 2

Reset to default
4
$\begingroup$

The sum of eigenvalues is equal to the trace, the sum of diagonal elements. Therefore, to get a trace of 8, all diagonal elements must be one. For a symmetric matrix, that leaves 28 unique symmetric off diagonal elements. This gives 2^28 different matrices.

To check, we may create a random binary matrix with all 1's on the diagonal and calculate the sum of eigenvalues:

n = 8;
mat = ConstantArray[0, {n, n}];
Do[mat[[i, j]] = 
   mat[[j, i]] = If[i == j, 1, RandomInteger[{0, 1}]], {i, n}, {j, i}];
Total@Eigenvalues[mat] // N

(* 8 *)
Improve this answer
$\endgroup$
2
  • $\begingroup$ We need to find the sum after finding the absolute value of each eigenvalue, not the direct sum of eigenvalues. In this case it is not the trace. Example: For the matrix {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}} its eigenvalues are 2 and -1, Here trace and sum of eigenvalues are 1. But sum of the absolute value of the eigenvalues is 3, which is same as the order of the matrix. We need to extract such matrices only. Is there any way to find such matrices only for n=8. $\endgroup$
    – SPJ
    Commented Apr 4, 2021 at 10:03
  • 1
    $\begingroup$ What this means is that there will be more than 2^28 such matrices. That's a big search space, though perhaps viable. $\endgroup$
    – Daniel Lichtblau
    Commented Apr 4, 2021 at 15:12
4
$\begingroup$

As suggested in the comments I've written a C code that searches through all symmetric binary 8x8 matrices and picks out the ones whose sum of absolute eigenvalues is equal to 8.

There are 547613 such matrices, if I did it correctly. If someone knows how to, I'll post the resulting matrices here. The compressed file is about 2 MB in size, too large for pastebin.

We need to be pretty careful with searching because there are some matrices like

{{0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 1},
 {0, 0, 0, 0, 0, 1, 1, 0},
 {0, 0, 0, 0, 1, 0, 0, 1},
 {0, 0, 0, 1, 0, 0, 1, 1},
 {0, 0, 0, 1, 0, 1, 1, 1},
 {0, 0, 1, 0, 1, 1, 1, 1}}

whose absolute eigenvalues sum to 7.99994, so the selection criterion must be chosen quite tightly.

C code

LAPACK-linked code for macOS: (different linking will be required for different operating systems to get LAPACK's ssyev to work)

#include <stdio.h>
#include <Accelerate/Accelerate.h>

/*
 * Compute eigenvalues of upper-triangle-defined symmetric matrix
 * Return sum of absolute eigenvalues
 */
static float sumabseigenvalues(int n, float *A)
{
  char char_n = 'n';
  char char_l = 'l';
  int lwork = 1024;
  float work[lwork];
  float eigenvalues[n];
  int info;
  ssyev_(&char_n, &char_l, &n, A, &n, eigenvalues, work, &lwork, &info);
  if (info!=0) return NAN;
  float s = 0;
  for (int i=0; i<n; i++)
    s += fabsf(eigenvalues[i]);
  return s;
}

static const float TOLERANCE = 5e-5;

int main()
{
  for (int m11=0; m11<2; m11++)
  for (int m12=0; m12<2; m12++)
  for (int m13=0; m13<2; m13++)
  for (int m14=0; m14<2; m14++)
  for (int m15=0; m15<2; m15++)
  for (int m16=0; m16<2; m16++)
  for (int m17=0; m17<2; m17++)
  for (int m18=0; m18<2; m18++)
  for (int m22=0; m22<2; m22++)
  for (int m23=0; m23<2; m23++)
  for (int m24=0; m24<2; m24++)
  for (int m25=0; m25<2; m25++)
  for (int m26=0; m26<2; m26++)
  for (int m27=0; m27<2; m27++)
  for (int m28=0; m28<2; m28++)
  for (int m33=0; m33<2; m33++)
  for (int m34=0; m34<2; m34++)
  for (int m35=0; m35<2; m35++)
  for (int m36=0; m36<2; m36++)
  for (int m37=0; m37<2; m37++)
  for (int m38=0; m38<2; m38++)
  for (int m44=0; m44<2; m44++)
  for (int m45=0; m45<2; m45++)
  for (int m46=0; m46<2; m46++)
  for (int m47=0; m47<2; m47++)
  for (int m48=0; m48<2; m48++)
  for (int m55=0; m55<2; m55++)
  for (int m56=0; m56<2; m56++)
  for (int m57=0; m57<2; m57++)
  for (int m58=0; m58<2; m58++)
  for (int m66=0; m66<2; m66++)
  for (int m67=0; m67<2; m67++)
  for (int m68=0; m68<2; m68++)
  for (int m77=0; m77<2; m77++)
  for (int m78=0; m78<2; m78++)
  for (int m88=0; m88<2; m88++) {
    float A[64];
    A[8*0 + 0] = m11;
    A[8*0 + 1] = m12;
    A[8*0 + 2] = m13;
    A[8*0 + 3] = m14;
    A[8*0 + 4] = m15;
    A[8*0 + 5] = m16;
    A[8*0 + 6] = m17;
    A[8*0 + 7] = m18;
    A[8*1 + 1] = m22;
    A[8*1 + 2] = m23;
    A[8*1 + 3] = m24;
    A[8*1 + 4] = m25;
    A[8*1 + 5] = m26;
    A[8*1 + 6] = m27;
    A[8*1 + 7] = m28;
    A[8*2 + 2] = m33;
    A[8*2 + 3] = m34;
    A[8*2 + 4] = m35;
    A[8*2 + 5] = m36;
    A[8*2 + 6] = m37;
    A[8*2 + 7] = m38;
    A[8*3 + 3] = m44;
    A[8*3 + 4] = m45;
    A[8*3 + 5] = m46;
    A[8*3 + 6] = m47;
    A[8*3 + 7] = m48;
    A[8*4 + 4] = m55;
    A[8*4 + 5] = m56;
    A[8*4 + 6] = m57;
    A[8*4 + 7] = m58;
    A[8*5 + 5] = m66;
    A[8*5 + 6] = m67;
    A[8*5 + 7] = m68;
    A[8*6 + 6] = m77;
    A[8*6 + 7] = m78;
    A[8*7 + 7] = m88;
    float s = sumabseigenvalues(8, A);
    if (fabsf(s-8) < TOLERANCE) {
      printf("{{%d,%d,%d,%d,%d,%d,%d,%d},{%d,%d,%d,%d,%d,%d,%d,%d},{%d,%d,%d,%d,%d,%d,%d,%d},{%d,%d,%d,%d,%d,%d,%d,%d},{%d,%d,%d,%d,%d,%d,%d,%d},{%d,%d,%d,%d,%d,%d,%d,%d},{%d,%d,%d,%d,%d,%d,%d,%d},{%d,%d,%d,%d,%d,%d,%d,%d}}\n",
             m11,m12,m13,m14,m15,m16,m17,m18,
             m12,m22,m23,m24,m25,m26,m27,m28,
             m13,m23,m33,m34,m35,m36,m37,m38,
             m14,m24,m34,m44,m45,m46,m47,m48,
             m15,m25,m35,m45,m55,m56,m57,m58,
             m16,m26,m36,m46,m56,m66,m67,m68,
             m17,m27,m37,m47,m57,m67,m77,m78,
             m18,m28,m38,m48,m58,m68,m78,m88);
    }
  }
  return EXIT_SUCCESS;
}

Save as binarymatrix.c and compile with

gcc binarymatrix.c -Ofast -framework Accelerate -o binarymatrix

and run with

./binarymatrix

producing lots of 8x8 matrices whose absolute eigenvalues sum to 8:

{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,0,1,1,1},{0,0,0,1,1,0,1,1},{0,0,0,1,1,1,0,1},{0,0,0,1,1,1,1,0}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,0,1,1,1},{0,0,0,1,1,0,1,1},{0,0,0,1,1,1,1,0},{0,0,0,1,1,1,0,1}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,0,1,1,1},{0,0,0,1,1,1,0,1},{0,0,0,1,1,0,1,1},{0,0,0,1,1,1,1,0}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,0,1,1,1},{0,0,0,1,1,1,1,0},{0,0,0,1,1,1,0,1},{0,0,0,1,1,0,1,1}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,1,0,1,1},{0,0,0,1,0,1,1,1},{0,0,0,1,1,1,0,1},{0,0,0,1,1,1,1,0}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,1,0,1,1},{0,0,0,1,0,1,1,1},{0,0,0,1,1,1,1,0},{0,0,0,1,1,1,0,1}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,1,1,0,1},{0,0,0,1,1,0,1,1},{0,0,0,1,0,1,1,1},{0,0,0,1,1,1,1,0}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,1,1,0,1},{0,0,0,1,1,1,1,0},{0,0,0,1,0,1,1,1},{0,0,0,1,1,0,1,1}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,1,1,1,0},{0,0,0,1,1,0,1,1},{0,0,0,1,1,1,0,1},{0,0,0,1,0,1,1,1}}
{{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1},{0,0,0,1,1,1,1,0},{0,0,0,1,1,1,0,1},{0,0,0,1,1,0,1,1},{0,0,0,1,0,1,1,1}}
...

Runtime was about 76 CPU-hours on my computer.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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