Serving the Quantitative Finance Community

  • 1
  • 2
  • 3
  • 4
  • 5
  • 7
 
User avatar
tw813
Topic Author
Posts: 5
Joined: August 26th, 2005, 12:15 am

Constructing an invertible positive matrix

April 3rd, 2018, 4:25 am

Hi

For a particular finance problem I am working on, I need to construct an invertible positive n-by-n matrix where positive means all matrix entries are positive.

Can any of you suggest a general approach to construct such matrices?
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Constructing an invertible positive matrix

April 3rd, 2018, 10:01 am

not sure if you have any other requirements.
Take a matrix where every element is [$]1[$] except for the diagonal entries as follows:

[$]a_{ij}=\left\{\matrix{1&i\ne j\cr j&i=j}\right.[$]
 
User avatar
Cuchulainn
Posts: 22929
Joined: July 16th, 2004, 7:38 am

Re: Constructing an invertible positive matrix

April 3rd, 2018, 4:54 pm

Even easier
[$]a_{ij}=\left\{\matrix{1&i=j\cr +0.00001&i\ne j}\right.[$]
 
User avatar
tw813
Topic Author
Posts: 5
Joined: August 26th, 2005, 12:15 am

Re: Constructing an invertible positive matrix

April 3rd, 2018, 6:34 pm

I understand these examples work. But wonder if there is any more systematic approach to generate a larger and more flexible class of such matrices, so that I can extract some of them with a structure that makes sense for for application.
 
User avatar
katastrofa
Posts: 7930
Joined: August 16th, 2007, 5:36 am
Location: Event Horizon

Re: Constructing an invertible positive matrix

April 3rd, 2018, 8:37 pm

I'm not sure if I follow, because it seems too obvious: if your matrix is has a non-zero determinant, it is invertible.
Is it a big matrix?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Re: Constructing an invertible positive matrix

April 3rd, 2018, 9:01 pm

You might consider doing the inverse of an eigendecomposition of a matrix (https://en.wikipedia.org/wiki/Eigendeco ... f_a_matrix) by constructing a set of eigenvectors and finding the eigenvalues that makes the recomposed matrix have entirely positive elements.
 
User avatar
katastrofa
Posts: 7930
Joined: August 16th, 2007, 5:36 am
Location: Event Horizon

Re: Constructing an invertible positive matrix

April 3rd, 2018, 11:05 pm

You can construct such a matrix from a set of linearly independent vectors [$]\vec v_i[$], where [$]v_{ij} \geq 0[$] and [$]||v_i|| =1[$].
You matrix [$]M = \sum \lambda_i P_i[$], where [$]\lambda_i>0[$] and [$]P_i = \vec v_i \vec v_i^T[$].

(corrected - blame the error on the posting time, my jetlag, Brexit and Tump :-))
Last edited by katastrofa on April 10th, 2018, 8:28 pm, edited 5 times in total.
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Constructing an invertible positive matrix

April 4th, 2018, 7:43 am

I understand these examples work. But wonder if there is any more systematic approach to generate a larger and more flexible class of such matrices, so that I can extract some of them with a structure that makes sense for for application.
the more you tell us about what you specifically require, the more likely it is that someone will be able to help you
What structure does make sense for your application?
The requirements listed in the initial post were
(a) square [$]n\times n[$]
(b) all entries positive, [$]a_{ij}>0[$] for all [$]i,j[$]
(c) invertible so rank(A)=n and det(A)[$]\ne 0[$]
What else?
cuch and I both suggested real symmetric matrices because real symmetric matrices have a full set of eigenvectors meaning they have rank n. But you need to make sure there are no zero eigenvalues
Absent any other specifications, we chose the simplest ones we could think of
 
User avatar
lovenatalya
Posts: 187
Joined: December 10th, 2013, 5:54 pm

Re: Constructing an invertible positive matrix

April 6th, 2018, 11:04 pm

You can construct such a matrix from a set of orthonormal vectors [$]\vec v_i[$], where [$]v_{ij} \geq 0[$].
You matrix [$]M = \sum \lambda_i P_i[$], where [$]\lambda_i>0[$] and [$]P_i = \vec v_i \vec v_i^T[$]. (The inverse is [$]M^{-1} = \sum \lambda_i^{-1} P_i[$].)
This is wrong in two respects. 
1. Two orthogonal vectors can not be both positive.
2. Ignoring point 1. , consider [$]M = \begin{bmatrix} a & -b \\ -b & a \end{bmatrix}[$] for [$]a>b>0[$]. 
 
User avatar
Cuchulainn
Posts: 22929
Joined: July 16th, 2004, 7:38 am

Re: Constructing an invertible positive matrix

April 7th, 2018, 8:03 am

You haven't really told us what the application/problem is. Matrix algebra is a big area.
Can you reduce the scope?

particular finance problem 
Describe it (guess: something to do with Perron-Frobenius theory and M matrices stuff?)

https://en.wikipedia.org/wiki/Perron%E2 ... us_theorem

such matrices?
Define such a class of matrices?

It's still clear as mud :)
 
User avatar
katastrofa
Posts: 7930
Joined: August 16th, 2007, 5:36 am
Location: Event Horizon

Re: Constructing an invertible positive matrix

April 7th, 2018, 8:37 am

You can construct such a matrix from a set of orthonormal vectors [$]\vec v_i[$], where [$]v_{ij} \geq 0[$].
You matrix [$]M = \sum \lambda_i P_i[$], where [$]\lambda_i>0[$] and [$]P_i = \vec v_i \vec v_i^T[$]. (The inverse is [$]M^{-1} = \sum \lambda_i^{-1} P_i[$].)
This is wrong in two respects. 
1. Two orthogonal vectors can not be both positive.
2. Ignoring point 1. , consider [$]M = \begin{bmatrix} a & -b \\ -b & a \end{bmatrix}[$] for [$]a>b>0[$]. 
I meant linearly independent vectors. Thanks for spotting this. I don't understand your second remark.
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Constructing an invertible positive matrix

April 7th, 2018, 10:21 am

where positive means all matrix entries are positive
I'd never come across this term, and it was never used in any of the linear algebra courses I took
wiki tells us that the term is not in standard use
While such matrices are commonly found, the term is only occasionally used due to the possible confusion with positive-definite matrices, which are different.
the Wikipedia page
https://en.wikipedia.org/wiki/Positive_matrix
doesn't even exist, it redirects to Non-negative
https://en.wikipedia.org/wiki/Nonnegative_matrix


for positive-definite matrices, all the eigenvalues are positive
It's possible for a matrix to be positive but not positive-definite
It's possible for a matrix to be positive-definite but not positive
 
User avatar
Cuchulainn
Posts: 22929
Joined: July 16th, 2004, 7:38 am

Re: Constructing an invertible positive matrix

April 7th, 2018, 1:02 pm

There's a large body of wok on positive matrices. e.g. in PDE/FDM the holy grail is to come up with a M-matrix (whose inverse is a positive matrix), thus leading to monotone schemes.

https://en.wikipedia.org/wiki/M-matrix

I constructed such schemes for convection-diffusion way back in the last century (e.g. BS) PDE that remain positive for any volatility and convection.

edit: The term 'positive' as applied to matrices is precise.
Attachments
DuffyExponentialFitting.pdf
(234.26 KiB) Downloaded 157 times
 
User avatar
lovenatalya
Posts: 187
Joined: December 10th, 2013, 5:54 pm

Re: Constructing an invertible positive matrix

April 7th, 2018, 6:13 pm

You can construct such a matrix from a set of orthonormal vectors [$]\vec v_i[$], where [$]v_{ij} \geq 0[$].
You matrix [$]M = \sum \lambda_i P_i[$], where [$]\lambda_i>0[$] and [$]P_i = \vec v_i \vec v_i^T[$]. (The inverse is [$]M^{-1} = \sum \lambda_i^{-1} P_i[$].)
This is wrong in two respects. 
1. Two orthogonal vectors can not be both positive.
2. Ignoring point 1. , consider [$]M = \begin{bmatrix} a & -b \\ -b & a \end{bmatrix}[$] for [$]a>b>0[$]. 
I meant linearly independent vectors. Thanks for spotting this. I don't understand your second remark.
In my point 2, without requiring [$]v_{ij} \geq 0[$], but keeping the orthonormality of [$]\vec v_i[$]'s, my matrix [$]M[$] can be eigen-decomposed exactly into the form of your specification and yet it has negative entries, contradicting your conclusion.

Now consider your new specification requiring [$]\vec v_i[$] to be only linearly independent. Do you still require [$]v_{ij} \geq 0[$]?  

3. If you do, you are doing nothing but presuming the question, i.e., finding invertible positive matrix. Your slight relaxation of the positive condition to nonnegative matrix as you allow for [$]v_{ij} \geq 0[$] rather than [$]v_{ij} > 0[$] not only does little to lessen the task,  but produces another counterexample. Consider the identity matrix [$]v_{ij} =\delta_{i,j}[$], which gives you nonpositive entries, i.e., [$]0[$] in the resulting matrix. 

4. If you do not, my counterexample in point 2. again negates this conjecture. 
Last edited by lovenatalya on April 8th, 2018, 9:44 pm, edited 1 time in total.
 
User avatar
lovenatalya
Posts: 187
Joined: December 10th, 2013, 5:54 pm

Re: Constructing an invertible positive matrix

April 7th, 2018, 6:28 pm

It is easy to systematically generate positive invertible matrix, if no other restrictions apply. Randomly pick any positive diagonal matrix. Randomly generate positive off-diagonal entries. Positively scale off-diagonal entries of each column and row so that their sum is less than the corresponding diagonal entry. Gershgorin circle theorem guarantees that all the eigenvalues have positive real part, making the matrix invertible.