CODEWITHSUNDEEP
javamathmatrixrandom
Imad Lamari
Imad Lamari

Reputation: 21

A random invertible matrix in Java

I work on a project, for this project I need to generate a square random invertible matrix.

I found out how to generate a square random matrix, still I want to be sure that this is an invertible one, without having to compute the determinant or to generate this matrix multiple times, can you please give me a tip?

Upvotes: 2

Views: 823

Answers (2)

Salix alba
Salix alba

Reputation: 7824

An LU decomposition might work.

Generate two matrices, L, which is lower triangular with all entries above the main diagonal zero and, U, an upper triangular matrix with entries below the main diagonal zero. Then form a matrix A=LU.

The determinant of either L or U is just the product of entries down the main diagonal so you just need to ensure none of these are zero. The determinant of A is the product of the two determinants.

Upvotes: 0

dmuir
dmuir

Reputation: 4431

One way is to generate the SVD of the matrix. That is you generate 'random' (square) orthogonal matrices U and V, and a 'random' diagonal matrix S, and then compute 

 M = U*S*V'

Note that every matrix has an SVD

As long as none of the diagonal elements of S are 0, M will be invertible. Many routines that deal with invertible matrices are sensitive to the condition number of the matrix; errors tend to increase as the condition number gets larger. The condition number of M is the same as the condition numner of S which is the largest (by absolute value) diagonal element of S divided by the smallest (by absolute value). You may want to control this. One way is to generate the elements of S to be uniform in say [lo,hi] and then randomly set the sign.

One way to generate 'random' orthogonal matrices is to generate then as a product of 'random' Householder reflections, that is matrices of the form

R_v = 1 - 2*v*v'/(v'*v)

where v is a 'random' vector. Every n by n orthogonal matrix can be written as a product of n Householder reflections. All this is not as computationally severe as it at first might look. Due to the special form of the reflectors it is straightforward to write routines that compute 

R_u*M and M*R_v'

in M using only n extra storage and being O( n * n)

So one scheme would be 

Generate S
Repeat n times
  Generate random non zero vector u 
  Update S to be R_u*S
  Generate random non zero vector v 
  Update S to be S*R_v'

Upvotes: 3

Related Questions