Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
3  
Pick a random matrix $A$ with small trace and use $e^A$. –  Quimey Jan 8 '13 at 20:33
1  
To make the determinant small (assuming full rank), divide each row by $10^N$. –  Calvin Lin Jan 8 '13 at 20:37
1  
@Quimey This uses $\det(\exp(A))=\exp(\mathrm{tr}(A))$? "Small" then should be taken to mean "as negative as possible", right? That's a neat approach. –  rschwieb Jan 8 '13 at 20:45
    
@rschwieb Yes, you are right. I can't edit my comment. –  Quimey Jan 8 '13 at 20:50
    
I have this vague notion in my memory that "most" random matrices you get by taking random values in $[0,1]$ are nearly singular. I can't conduct the experiment though :/ Did you try square matrices with random values in an interval? –  rschwieb Jan 8 '13 at 20:54

3 Answers 3

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$.

share|improve this answer

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.)

share|improve this answer
    
An upper triangular matrix with 1's on the diagonal is certainly a very easy-to-implement method! If the poster is willing to use numbers other than integers (which I cannot tell from the post) then this could be tweaked a little more by generating numbers for the diagonal randomly in $(0,\epsilon)$ where $\epsilon$ is as small as your computer can tolerate for error. –  rschwieb Jan 8 '13 at 21:28

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$.

share|improve this answer
    
Ah, I think I see. It should be "set $A(m,m)=1$". Each step uses a randomly selected row or column, and copies it. The $d-\mathbf{c} A^{-1} \mathbf{b}$ (portion of determinant update formula) value of the new determinant is one, thus no change in overall determinant, and the shuffle hides that small reference to the previous state. Cool. –  adam W Jan 9 '13 at 2:56
    
@adamW Yes, it's a typo. Just set $A(m,m)=1$. –  user1551 Jan 9 '13 at 7:44
    
@adamW For the record, it was indeed my plan to use Schur complement to update the determinant, and it worked, but didn't work nicely. So the current answer is based on Laplace expansion of determinant rather than rank 1 update. My original plan is this: we begin with $A(1,1)=1$. Then use the trick in the current answer to build an $(n-1)\times(n-1)$ matrix with absolute determinant 1. Then choose the last row and last column randomly, with each entry equals to 1 with some probability $p$. The final determinant is then equal to the Schur complement. –  user1551 Jan 9 '13 at 18:01
    
Yet there are two problems. First, I have to compute a matrix inverse for each $m$, which is costly. Second, it is hard to tell what are inside $A^{-1}$. Although we can restrain the size of $c^TA^{-1}b$ by controlling $p$, it is difficult to tell which $p$ is optimal. So, the extent of control is not as good as the current answer and large determinants may be obtained at times. –  user1551 Jan 9 '13 at 18:01
    
Your answer here works, correct? I like it quite a bit. Why do you say it does not work nicely? I am guessing you want unit determinant? I have that for up to 20 or 30 dimensions, we may need to go to chat or elsewhere for me to explain. As for matrix inverse for each $m$, and $A^{-1}$, they are computable as rank one updates all along the way, so not terribly costly. The Laplace expansion is contained within and gives the determinant of the rank one update, see my other answer to your question where the vector $\mathbf{x}$ is that expansion. –  adam W Jan 9 '13 at 18:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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