Matrix generator for a specific determinant

closed account (zv05oG1T)
I tried to generate a matrix with the code below. It works, but it has some isues. One of them is that for a matrix NxN, the code generates random elements, but it generates the same matrix, for the same n.
For example: n=3, it generates the matrix:
-1 0 2
-2 2 2
1 1 0
I thought next time i generate a new 3x3 matrix, it will be different, but it's always the same. Still, that's not the problem. Even if it wasn't this problem, i need an algorithm which generates an invertible matrix. Additionally, i need the determinant=1. I have to use the inverse matrix. So, if the determinant is not equal 1, it will be more difficult to finish the program.

1
2
3
  for (i=0;i<n;i++)
	for(j=0;j<n;j++)
	m[i][j]=rand()%5- 2;
> I thought next time i generate a new 3x3 matrix, it will be different, but it's always the same
┬┐are you sedding the random number generator?


> i need an algorithm which generates an invertible matrix.
create a triangular matrix, then operate with the rows.

> Additionally, i need the determinant=1.
do M/det(M)
closed account (zv05oG1T)
that's the code for invertible matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
ofstream g ("inv.txt");
float determinant(float matrix[30][30],float size)
{
    float s=1,det=0,m_minor[30][30];
	int i,j,m,n,c;
    if (size==1)
    {
        return (matrix[0][0]);
    }
    else
    {
        det=0;
        for (c=0;c<size;c++)
        {
            m=0;
            n=0;
            for (i=0;i<size;i++)
            {
                for (j=0;j<size;j++)
                {
                    m_minor[i][j]=0;
                    if (i != 0 && j != c)
                    {
                       m_minor[m][n]=matrix[i][j];
                       if (n<(size-2))
                          n++;
                       else
                       {
                           n=0;
                           m++;
                       }
                    }
                }
            }
            det=det + s * (matrix[0][c] * determinant(m_minor,size-1));
            s=-1 * s;
        }
    }
 
    return (det);
}
void transpose(float matrix[30][30],float matrix_cofactor[30][30],float size)
{
     int i,j;
	 float m_transpose[30][30],m_inverse[30][30],d;
 
     for (i=0;i<size;i++)
     {
         for (j=0;j<size;j++)
         {
             m_transpose[i][j]=matrix_cofactor[j][i];
         }
     }
     d=determinant(matrix,size);
     for (i=0;i<size;i++)
     {
         for (j=0;j<size;j++)
         {
             m_inverse[i][j]=m_transpose[i][j] / d;
         }
     }
     cout<<"\nThe inverse matrix is : \n";
 	
     for (i=0;i<size;i++)
     {
         for (j=0;j<size;j++)
         {
             cout<<m_inverse[i][j]<<" ";
             g<<m_inverse[i][j]<<" ";
         }
         cout<<endl;
         
     }
g.close(); cout<<endl;
}

void cofactor(float matrix[30][30],float size)
{
     float m_cofactor[30][30],matrix_cofactor[30][30];
	 int p,q,m,n,i,j;
     for (q=0;q<size;q++)
     {
         for (p=0;p<size;p++)
         {
             m=0;
             n=0;
             for (i=0;i<size;i++)
             {
                 for (j=0;j<size;j++)
                 {
                     if (i != q && j != p)
                     {
                        m_cofactor[m][n]=matrix[i][j];
                        if (n<(size-2))
                           n++;
                        else
                        {
                            n=0;
                            m++;
                        }
                     }
                 }
             }
             matrix_cofactor[q][p]=pow(-1,q + p) * determinant(m_cofactor,size-1);
         }
     }
     transpose(matrix,matrix_cofactor,size);
}
closed account (zv05oG1T)
I have to generate matrix NxN with the determinant=1, each time a different matrix
Do you have any conditions that the matrices must meet beyond their being invertible? For example, it seems like you could pick a single non-zero random number x0 and then generate the matrix
x0 0 0 ...
0 x0 0 ...
0 0 x0 ...
... ... ... ...
closed account (zv05oG1T)
That won't work. I can have some zeroes in matrix, but i can't have too many. My program encodes a message, assigning one number to each character. Then, i have to multiply those numbers with the matrix. For example: I want to encode the message: "That's my program!"; it will display: 20 727 506 454 149 481 321 314 77 657 495 406 162 727 509 430 147 79 78 1 0. Too many zeroes means losing the message...
Last edited on
Too many zeroes means losing the message...
Well, no. You will only lose information if the matrix is non-invertible. That's what it means for a matrix to be invertible.

Any invertible matrix can be reduced to an equivalent diagonal matrix
x0 0 0 ... 0
0 x1 0 ... 0
0 0 x2 ... 0
... ... ... ... 0
0 0 0 0 xn
where x0, x1, ..., xn are non-zero reals. Therefore, for a message of length n, all you need to do is generate n non-zero reals; then treating the plaintext as a vector and multiplying it by that diagonal matrix is equivalent to doing cyphertext[i] = plaintext[i] * M[i][i]

I will advice that this is way, way more inefficient a one-time pad with XOR.
closed account (zv05oG1T)
Random diagonal matrix means invertible matrix, but it also means random determinant. If the determinant is not equal 1 or -1, there will be an inverse matrix, type float. I need random matrix with the determinant=1 or -1. Still, you gave me a great idea. I'll try to generate diagonal matrices which contain only the elements 1 and -1.
closed account (zv05oG1T)
That should do the trick.
1
2
for (i=0;i<n;i++)
	 a[i][i]=pow(-1,rand()%100);
Random diagonal matrix means invertible matrix, but it also means random determinant. If the determinant is not equal 1 or -1, there will be an inverse matrix, type float. I need random matrix with the determinant=1 or -1.
As a counter-example, the matrix
2 0
0 1
has a determinant equal to 2, but also has an inverse:
0.5 0
0 1
The condition for invertibility is det(M) != 0.

If you still want to force det(M) = k for whatever reason, simply pick non-zero reals x0, x1, ..., xn-1, then xn = k/(x0 * x1 * ... * xn-1).

I'll try to generate diagonal matrices which contain only the elements 1 and -1.
This is really bad. Do not do this. Half of your cyphertext will be just be the same as the plaintext.
closed account (zv05oG1T)
Yeah, not a good idea... I really need det(M)=1 or -1.
If you still want to force det(M) = k for whatever reason, simply pick non-zero reals x0, x1, ..., xn-1, then xn = k/(x0 * x1 * ... * xn-1).
I'll try this. Thank you!
Topic archived. No new replies allowed.