Nonnegative rank (linear algebra)

In linear algebra, the nonnegative rank of a nonnegative matrix is a concept similar to the usual linear rank of a real matrix, but adding the requirement that certain coefficients and entries of vectors/matrices have to be nonnegative.

For example, the linear rank of a matrix is the smallest number of vectors, such that every column of the matrix can be written as a linear combination of those vectors. For the nonnegative rank, it is required that the vectors must have nonnegative entries, and also that the coefficients in the linear combinations are nonnegative.

YouTube Encyclopedic

1/3
Views:
58 845
189 955
2 663

Transcription

MARTINA BALAGOVIC: Hi. Welcome to recitation. Today's problem is about positive definite matrices. And it's asking us, for which values of the parameter c, which is sitting here in the matrix, is the matrix B, 2, minus 1, minus 1, minus 1, 2, minus 1, minus 1, minus 1, 2 plus c, positive definite, and for which values of c is it positive semidefinite? I'm going to leave you alone with the problem. You should pause the video and then come back and compare your solution. And we're back. As you remember from the lectures, there are several tests that you can do on matrices to find out if they're positive definite and if they're positive semidefinite. And I'm going to demonstrate three to you. First, I'm going to do the one that you should do in case you have very little time and you're asked to do a problem like this on the test, which is of course the determinant test. The determinant test asks us to compute determinants of the matrices in the upper left corner of all sizes. And it says that it's going to be positive definite if they're all greater than 0 and positive semidefinite if some 0's sneak into into that sequence. So let's calculate the determinants. The first determinant is the determinant of this tiny matrix here. So it's just 2. The next one is the determinant of this two by two submatrix, 2, minus 1, minus 1, 2, which is equal to 4 minus 1, which is 3. And finally, we have the determinant of B, which I'm going to calculate for you. I'm going to calculate it, I'm going to decompose it along the first line, first row. So it's 2 times the determinant of this submatrix, 2, minus 1, minus 1, 2 plus c, minus minus 1, this one here, times this determinant, which is minus 1, minus 1, minus 1, 2 plus c. And then plus minus 1, this one here, times this determinant, which is minus 1, 2, minus 1, minus 1. And in total, that's 2 times 4 plus 2c minus 1 plus minus 2 minus c minus 1 and minus 1 plus 2. And in total, this should give us 6 plus 4c minus 3 minus c minus 3, which is 3c. So let's look at the determinants. 2 is positive. 3 is positive. 3c is positive. So the answer is the matrix is positive definite if c is bigger than 0, and it's positive semidefinite if it's either strictly bigger than 0 or equal to 0. And that's all. If you're on the test, this is everything that you should do. Now let me show you two more tests to demonstrate that first, they take longer, and second, to see these numbers and their quotients show up in other tests and to try to convince you that these tests really are equivalent. Let me do the pivots test for you. So we take our matrix B, 2, minus 1, minus 1, minus 1, 2, minus 1, minus 1, minus 1, 2 plus c. And let's pretend we're solving a system that has this as a matrix. So we multiply the first row by 1/2, and we add it to the second and to the third row. We get 2, minus 1, minus 1, 0, 3/2, minus 3/2, 0, minus 3/2, 3/2 plus c. So the first column is good. And then we just replace the third column with the third column plus the second column. And we get 2, minus 1, minus 1, 0, 3/2, minus 3/2, 0, 0, and c. And so the pivots are 2, 3/2, and c. And again, the answer is as before. It's positive definite if c is strictly bigger than 0, and it's positive semidefinite if c is greater or equal to 0. But I want you to notice something else here. So before, we had 2, 3, and 3c. And now for determinants, as these pivots, we have 2, 3/2, which is the second determinant over the first determinant, and c, which can be thought of as 3c/3, so the third determinant over the second determinant. And something like this is always going to happen. And finally, let me do the energy test, or completing the square. So one of the definitions of positive definite, one could say the definition because of which we are really interested in such matrices, is the following. It's positive definite if when we consider this quadratic form, so a form that maps x, y, and z to this expression here that's going to be quadratic in x, y, and z, it's positive semidefinite if this is always greater or equal than 0. And it's positive definite if, when we have an expression like this and try to solve this equals 0, the only solution is that x, y, and z all have to be 0. So let's try calculating this form, completing the squares on it, and seeing these numbers show up again. So when I multiply this like this, put in a B, do the multiplication, we get something like this. 2x squared plus 2y squared plus 2 plus c z squared minus 2xy minus 2xz minus 2yz. And now let's try completing the squares using the formulas that I prepared for you up here in this pop-up window in the corner. So let's try completing, we have a formula for the square of a plus b plus c and the square of a plus b. So first, we try to get something squared so that this something has all the x's that appear here, so that we get something squared plus some expression that only takes y's and z's. I'm not going to do the calculation in front of you, further embarrass myself with it. But let me tell you that what you get is 2 times x minus 1/2 y minus 1/2 z squared. And this ate all the x's that showed up here. The remainder only has y's and z's. When you use the second of those formulas in a pop-up window to complete the square of y's and z's, you get 3/2 times y minus z squared. So this took up all the y's, and we're left just with a z that comes as c times z squared. And now, let's look at the following. This is a square of some real number. So that's positive. This is a square of some real number, so that's positive. And this is a square of some real number, so that's positive. They're all multiplied by positive numbers, 2, 3/2, and c, which we've already seen here. And so if c is bigger or equal than 0, this is certainly always bigger or equal than 0. Now to the question of if this can be equal to 0 without x, y, and z all being 0, well, let's look at two cases. If c is strictly bigger than 0, then let me write this matrix here as 2, 3/2 and c times 1, minus 1/2, minus 1/2, 0, 1, minus 1, and 0, 0, 1. Let's imagine c is strictly bigger than 0. And let's see when can this expression be equal to 0. Well, as we said, it's a sum of certain squares. They're all greater or equal to 0, so they all have to be equal to 0 for this expression to be 0. In other words, z needs to be equal to 0. y minus z needs to be equal to 0. And x minus 1/2 y minus 1/2 z also needs to be equal to 0. And since this matrix has all the pivots, this can only happen if x, y, and z are all equal to 0. On the other hand, if c is equal to 0, then let me write this matrix here again. Take 2 out here. Take 3/2 out here. And write again 1, minus 1/2, minus 1/2, 0, 1, minus 1, and 0, 0, 0. And so imagining that c is 0, when can this whole expression be equal to 0? Well, the last bit is already 0. We need to have y minus z equal to 0. And we need to have 1 times x minus 1/2 times y minus 1/2 times z also equal to 0. So we need to have x, y, z in the kernel of this matrix. But this matrix only has two pivots. It has one free variable. So we can find a solution to this times x, y, z equals 0 that's not 0 itself. Namely, if you remember how to solve systems like this, we set z equal to 1. From this, we calculate that y has to be 1. And then from this, we calculate that x has to be 1. And you can check that for in case c is 0, this thing here, when you plug it in here, you really get 0. In fact, this thing here is in the kernel of the matrix B. In fact, in case c is 0, the columns of matrix B sum up to 0 because of this here. And that's all I wanted to say for today.

Formal definition

There are several equivalent definitions, all modifying the definition of the linear rank slightly. Apart from the definition given above, there is the following: The nonnegative rank of a nonnegative m×n-matrix A is equal to the smallest number q such there exists a nonnegative m×q-matrix B and a nonnegative q×n-matrix C such that A = BC (the usual matrix product). To obtain the linear rank, drop the condition that B and C must be nonnegative.

Further, the nonnegative rank is the smallest number of nonnegative rank-one matrices into which the matrix can be decomposed additively:

{\mbox{rank}}_{+}(A)=\min\{q\mid \sum _{j=1}^{q}R_{j}=A,\;{\mbox{rank}}\,R_{1}=\dots ={\mbox{rank}}\,R_{q}=1,\;R_{1},\dots ,R_{q}\geq 0\},

where R_j ≥ 0 stands for "R_j is nonnegative".^[1] (To obtain the usual linear rank, drop the condition that the R_j have to be nonnegative.)

Given a nonnegative $m\times n$ matrix A the nonnegative rank $rank_{+}(A)$ of A satisfies

{\mbox{rank}}\,(A)\leq {\mbox{rank}}_{+}(A)\leq \min(m,n),

where

{\mbox{rank}}\,(A)

denotes the usual linear rank of A.

A Fallacy

The rank of the matrix A is the largest number of columns which are linearly independent, i.e., none of the selected columns can be written as a linear combination of the other selected columns. It is not true that adding nonnegativity to this characterization gives the nonnegative rank: The nonnegative rank is in general less than or equal to the largest number of columns such that no selected column can be written as a nonnegative linear combination of the other selected columns.

Connection with the linear rank

It is always true that rank(A) ≤ rank₊(A). In fact rank₊(A) = rank(A) holds whenever rank(A) ≤ 2.

In the case rank(A) ≥ 3, however, rank(A) < rank₊(A) is possible. For example, the matrix

$\mathbf {A} ={\begin{bmatrix}1&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&1\end{bmatrix}},$

satisfies rank(A) = 3 < 4 = rank₊(A).

These two results (including the 4×4 matrix example above) were first provided by Thomas in a response^[2] to a question posed in 1973 by Berman and Plemmons.^[3]

Computing the nonnegative rank

The nonnegative rank of a matrix can be determined algorithmically.^[4]

It has been proved that determining whether ${{\text{rank}}_{+}}(A)={\text{rank}}(A)$ is NP-hard.^[5]

Obvious questions concerning the complexity of nonnegative rank computation remain unanswered to date. For example, the complexity of determining the nonnegative rank of matrices of fixed rank k is unknown for k > 2.

Ancillary facts

Nonnegative rank has important applications in Combinatorial optimization:^[6] The minimum number of facets of an extension of a polyhedron P is equal to the nonnegative rank of its so-called slack matrix.^[7]

References

^ Abraham Berman and Robert J. Plemmons. Nonnegative Matrices in the Mathematical Sciences, SIAM
^ L. B. Thomas. "Solution to Problem 73-14, Rank Factorization of Nonnegative Matrices", SIAM Review 16(3), 393-394, 1974
^ Berman, A., Plemmons, R.J.: "Rank Factorization of Nonnegative Matrices", SIAM Review 15(3), 655, 1973
^ J. Cohen and U. Rothblum. "Nonnegative ranks, decompositions and factorizations of nonnegative matrices". Linear Algebra and its Applications, 190:149–168, 1993.
^ Stephen Vavasis, On the complexity of nonnegative matrix factorization, SIAM Journal on Optimization 20 (3) 1364-1377, 2009.
^ Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci., 43(3):441–466, 1991.
^ See this blog post Archived 2014-10-07 at the Wayback Machine

This page was last edited on 5 November 2021, at 18:28

From Wikipedia, the free encyclopedia