How to randomly construct a square full-ranked matrix with low determinant?

Question

How to randomly construct a square (1000*1000) full-ranked matrix with low determinant?

I have tried the following method, but it failed.

In MATLAB, I just use:

n=100;

A=randi([0 1], n, n);

while rank(A)~=n

A=randi([0 1], n, n);

end

The above code generates a random binary matrix, with the hope that the corresponding determinant can be small.

However, the determinant is usually about 10^49, a huge number.

Not to mention when n>200, the determinant is usually overflowed in MATLAB.

Could anyone have comments how I can generate matrix (could be non-binary) with very low determinant (e.g. <10^3)?

Answer 1

The determinant of $e^B$ is $e^{\textrm{tr}(B)}$ (wiki) and $e^B$ is always invertible, since $e^B e^{-B}=\textrm{Id}$. So, if you have a matrix $B$ with negative trace then $\det e^B$ is positive and smaller than $1$. Using this idea I wrote the following matlab script which generates matrices with "small" determinant:

n=100;
for i=1:10
    B=randn(n);
    A=expm(B);
    det(A)
end

I generate the coefficients using a normal distribution with mean $0$, so that the expected trace of B is $0$ (I think) and therefore the expected determinant of $A$ is $1$.

Answer 2

One possibility: Generate a lower triangular matrix with ones on the diagonal. Generate an upper triangular matrix with ones on the diagonal. The multiple would be a matrix with determinant of one.

This would look a bit non-random when inspected as the lower right corner elements would be larger than the upper left. But the idea gives you control over what determinant you obtain. You could scale the triangular matrices appropriately elementwise to compensate.

Second possibility: If you want to calculate an inverse (maybe just generate a matrix and inverse some other less expensive way) then do $PDP^{-1}$ and the result has determinant same as $D$ a diagonal matrix. Be careful not to use $D=I$ as you will only obtain the identity again.

Third possibility: perform random elementary row operations on the identity matrix (or another $D$ of desired determinant.)

Answer 3

Here is a way to generate full rank 0-1 random matrices with small absolute determinants. We will adopt Matlab's notations for row/column indexing. Suppose the target matrix $A$ is $n\times n$. From numerical experiments, we see that the mean absolute value of the determinant of a random $20\times20$ binary matrix is about $3600$, whose order of magnitude is about the OP's desired upper bound. So the idea is to begin with a $k\times k$ random matrix with $k\le20$ and low absolute determinant, then expand it to an $n\times n$ full rank matrix with the same absolute determinant. The details are as follows:

1. Initialize $A$ to the zero matrix.
2. Pick a random size $k\in\{1,2,\ldots,20\}$ and set $A(1:k,\,1:k)$ to a random 0-1 matrix. Repeat this step until $|\det A(1:k,\,1:k)|$ is nonzero and smaller than the required upper bound. (You may use a weighted sample of $k$ to adjust the distribution of the absolute determinant.)
3. For $m=k+1,\ldots,n$, generate the last row and last column of the submatrix $A(1:m,\,1:m)$ as follows:
   1. Pick a random number in $\{0,1\}$.
   2. If the outcome is $0$, do the following:
      1. Pick a column index $j\in\{1,\,\ldots,\,m-1\}$ at random.
      2. Set $A(1:(m-1),\,m)=A(1:(m-1),\,j)$ and set $A(m,m)=1$.
      3. For each $k\in\{1,\,\ldots,\,m-1\}$ with $k\not=j$, randomly set $A(m,k)=0$ or $1$.
      4. Permute the columns of $A(1:m,\,1:m)$ at random. Or you may just interchange $A(1:m,\,m)$ with some $A(1:m,\,k)$, where $k\in\{1,\,\ldots,\,m-1\}$ is chosen at random.
   3. If the outcome is $1$, perform the analogous procedure to step 3.2 in a "transposed" fashion. In other words, first set $A(m,\,1:(m-1))$ equal to some $A(i,\,1:(m-1))$ and $A(m,m)=1$, then set the entries of $A(m,:)$ (except the $i$-th one and the $m$-th one) to $0$ or $1$ at random. Then permute the rows of $A(1:m,\,1:m)$ at random.

I have run a numerical experiment on my computer to generate 0-1 matrices of order 100. If $A$ is chosen entirely at random, the average absolute determinant over 1000 samples is about $2.4\times10^{49}$. Using the above procedure, however, the average absolute determinant is only $97.6$ when the imposed upper bound is $1000$.