How to find a matrix D with m rows and n columns, with entries 1 and -1 only, which det(D'*D)=5-CodePudding

I have created a 5x4 matrix with entries only 1 and -1. I have also created the code which gives me randomly possible configurations for this kind of matrix. Every time I check manually if the determinant of the D'*D product is equal to 512 or not. Until now, I have only got the results of determinants 0, -64, 192 and -128.

I want to get the matrix configurations automatically: whose determinant is equal to 512, whose determinant is between 0 and 512.

So far I have done this line of code. It is right, even though I have to run the code by myself after each calculation.

valueset = [1,-1];
desiredsize = [5, 4];
desiredmatrix = valueset(randi(numel(valueset), desiredsize))
b=desiredmatrix.'
a=desiredmatrix.'*D
det(a)

and I got these kinds of calculations:

>desired

desiredmatrix =

   1  -1   1  -1
   1  -1   1  -1
  -1  -1   1  -1
   1  -1  -1  -1
   1   1  -1  -1

b =

   1   1  -1   1   1
  -1  -1  -1  -1   1
   1   1   1  -1  -1
  -1  -1  -1  -1  -1

a =

   1   3   3   1
  -1   1  -3  -5
  -1  -3   1   3
  -3  -1  -5  -3

ans = 64
> desired

desiredmatrix =

  -1   1   1   1
   1   1   1   1
  -1  -1   1   1
   1  -1  -1  -1
   1  -1  -1  -1

b =

  -1   1  -1   1   1
   1   1  -1  -1  -1
   1   1   1  -1  -1
   1   1   1  -1  -1

a =

   3   1   1  -1
  -3  -1  -1   1
  -1  -3   1   3
  -1  -3   1   3

ans = 0

etc, etc

CodePudding user response：

It takes me around 23 milliseconds to compute first such matrix. And about 29-30 seconds to find all such matrices.

Now, we have 20 values in a matrix, so we have 2^20=2048 such matrices.

So I run a for loop first to iterate through all these numbers (0 to 2047). Now we go to fill the matrix. Now each i in the first for loop, I take the binary representation of i and pad it with 0s till I get a 20-element binary list.

So, 140 who's binary is 10001100 will become a list of 0000 0000 0000 1000 1100 (spaces added for visibility) which will be, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0] (say its named bin_list)

Now, to fill the 20 elements of my matrix (say 0 to 19) I fill the jth element as valueset[bin_list[j]] so if the element of bin_list is 0, the corresponding element of my array A is 1 and if its 1 then A gets the value (-1). So, for the case of 140, the matrix A will be

[[ 1,  1,  1,  1],
 [ 1,  1,  1,  1],
 [ 1,  1,  1,  1],
 [-1,  1,  1,  1],
 [-1, -1,  1,  1]]

Note: I have to convert A into a matrix using numpy.matrix since we need to calculate transpose and determinant

After calculating this matrix A, I calculate the transpose using numpy.transpose(), say it is B. now I calculate the determinant using numpy.linalg.det(B*A). Now due to the return datatype of numpy.linalg.det(), I round it off to the nearest integer.

I check if this determinant is 512. If it is, bingo, I have the correct matrix.

The first solution I have is 854 (i=854) The bin_list for this would be, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0]

The matrix A would be,

matrix([[ 1,  1,  1,  1],
       [ 1,  1,  1,  1],
       [ 1,  1, -1, -1],
       [ 1, -1,  1, -1],
       [ 1, -1, -1,  1]])

A'*A will be,

matrix([[5, 1, 1, 1],
        [1, 5, 1, 1],
        [1, 1, 5, 1],
        [1, 1, 1, 5]])

The determinant of this will be 512 (after converting the determinant into an int)

The code for converting 140 to the binary list is:

def int_to_binlist(n, b = 8):
    res=[]
    strb = str(b) 'b'
    str1 = format(n, strb)
    res = list(map(int, list(str1)))
    return res

The code snippet for filling the matrix A with the bits of 1 and -1 is,

n_mat = desiredsize[0]*desiredsize[1] #so 5*4=20
for j in range(n_mat):
    a[int(j/4)][j%4] = valueset[li[j]]

References: numpy.linalg.det documentation numpy.matrix documentation