2
votes
0answers
29 views

Rayleigh Quotient variant?

If $A$ is a covariance matrix and I want to get $\max X^TAX$ where each value of $x$ is between -1 and 1. Is there a closed-form solution for this? I understand when $X^TX = 1$ this becomes the ...
1
vote
0answers
9 views

Symbol or name for Basismatrix of Linear Programming

This question is about the Basismatrix in the context of Linear Programming. Basically (haha!) we have the Matrix of the standard (or normal) form, which consists of (A|E) with the coefficient matrix ...
1
vote
1answer
14 views

the differences and relationship between linear independent and affinely independent

When learning optimization, I heard the two related concepts on linear algebra: linearly independent and affinely independent. ...
1
vote
0answers
49 views

Formula for position in an upper triangular matrix

I'm currently working on the Travelling Salesman's Problem in a computer science module. I have implemented some linear programming techniques using the software lp_solve. I've ended up with an upper ...
1
vote
0answers
24 views

Matrix multiplication in game theory doesn't add up? Min y^T*Ax

I'm studying game theory and something seems weird to me. My book says y is the probability of the row player and x is the probability of column player, both x and y are vectors. A = [a$_i$$_j$] is ...
0
votes
1answer
21 views

Duality and Optimality Conditions

I have seen the solution and it involves adding a $x_5$ and $x_6$ to the inequalities. I really do not understand why this happens? I have not seen any questions like this yet. Any pointers would ...
2
votes
0answers
47 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
1
vote
1answer
49 views

Exploiting structure of linear equations to solve them

So I have a bunch of linear equations $Ax=y : A \in R^{m,m}, y \in R^{m}$. Note that $A$ is a square matrix. The question is if I can decompose $A$ as $$A = D + uv^T$$ where $D$ is diagonal, ...
0
votes
0answers
28 views

totally uni modular matrices with binary variables

I have this problem A*X<=B A is totally uni modular matrix, X is binary vector { 0 , 1} values . any help for finding polynomial algorithm for solving this problem?
1
vote
1answer
48 views

Does the identity matrix adapt to any other matrix?

So I have a matrix of the form $X=AX+B$ Where $X$ is a 3 by 1 column matrix, $A$ is a 3 by 3 matrix and $B$ is a 3 by 1 column matrix. (Notice that I am talking about Leontief input-output). So I ...
2
votes
0answers
33 views

Showing a Hermitian preserving map is not necessarily positivity preserving?

Say I have a linear map, which is not positivity preserving $$\phi: \mathscr H \to \mathscr H$$where $\mathscr H$ is the set of $n \times n$ Hermitian matrices. Then does there exist a positive ...
6
votes
1answer
85 views

Why is there n-1 different objects in a n by n matrix game like Bejeweled?

For games that consists of a grid, and is similar to the concept like bejeweled: has an n by n matrix and n-1 different objects. What is the reason for this? Why not have more than n-1 different ...
1
vote
0answers
33 views

Is the coefficient uniquely determined by the sign function?

Suppose $a\in R^p$, $b\in R^p$, and $||a||=||b||=1$, is it true that if $sign(a'x)=sign(b'x)$ for any $x\in R^p$, then $a=b$, where $sign(t)=1$ if $t\geq 0$ and $sign(t)=-1$ if $t<0$?
1
vote
0answers
40 views

How to solve linear system of equations in 1 and inf-norm?

I have the problem to find a linear program that is equivalent to solving the problem that finds a minimum for $||Ax-b||_1$ and $||Ax-b||_{\infty}$. We defined a linear program as follows: $min_{x} ...
1
vote
2answers
75 views

How to determine this?

For any 6 coplanar points $\left(x_{1}+y_{1},x_{2}+y_{2},x_{3}+y_{3}\right)$, $\left(x_{1}+y_{2},x_{2}+y_{1},x_{3}+y_{3}\right)$,$\left(x_{1}+y_{3},x_{2}+y_{2},x_{3}+y_{1}\right)$, ...
1
vote
0answers
14 views

How to find the best fit when you have a set of ideal ratios, but some of those are below a minimum?

Say you have a set of ideal ratios, whose sum = 1. For example, input = [0.2, 0.2, 0.3, 0.3] But suppose that there is a rule stating that every ratio should be ...
1
vote
0answers
30 views

If the following LP has an integral solution

I know the constraints matrix A of a linear program "Min cx such that Ax>=b" is totally unimodular. So, the program has integral solutions for integral vector b. If this is also the case for the ...
0
votes
0answers
162 views

Solving an overdetermined system of inequalities using null-space arguments

The solutions to a linear system of equations: $$A\cdot x = b$$ (where $x$ is a $(n\times 1)$ column vector, $b$ is a $(m\times 1)$ column vector and $A$ is $(m\times n)$ matrix) can all be ...
2
votes
1answer
2k views

Armijo's rule line search

I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13. The variable is $\beta$ ...
2
votes
1answer
309 views

Polytopes and matrices

How can one show that the vertices of a polytope are the matrices contains 2 ones on each row and col? and if $M \in P$ is not a $Z_2$ matrix then $M$ is a derived ...
0
votes
1answer
813 views

Matlab question: Converting a permutation matrix into a vector showing row exchanges

Let me preface that I am an absolute beginner with Matlab. I am trying to perform $PA=LU$ factorization on a matrix, however I am having difficulty with the permutation matrix. When I execute ...
4
votes
1answer
522 views

How to solve system of equations with multiple constraints?

I have a system of equations that looks like this: $$\begin{array}{rl} a_1 b_1 c_1+a_2 b_2 c_2+a_3 b_3 c_3&=1000\\ a_1+a_2+a_3&=1\\ a_2&=0.6 \,a_1\\ b_1+b_2+b_3&=500 \end{array}$$ ...
1
vote
2answers
343 views

Invertability of submatrix?

If I have a matrix $A \in R^{(m \times n)}$ with $m \leq n$. All rows in matrix a are linearly independent and therefore $A$ has a full row rank. I can decompose matrix $A$ such that $A = [B|N]$ with ...
3
votes
0answers
49 views

finding the largest $p$ components of $x$

Given an $n \times n$ matrix $A$, and an $n \times 1$ vector $b$, the conventional way of computing an $n \times 1$ vector $x$ such that $x=Ax+b$ is to use the following iterations: ...
3
votes
1answer
215 views

Dimension of solution space for system of linear inequalities

Let's say I have a system of inequalities: $Ax \leq g$ for some $A \in \mathbb{R}^{4\times4}$, $x \in \mathbb{R}^4$, $g \in \mathbb{R}^4$, and $A$ is full rank. Here, the $\leq$ denotes element-wise ...
0
votes
1answer
31 views

intuitive explanation of sparsity / references

I know it is a vague question, but I am confused by why/when we actually want sparsity of a matrix. For example, interior-point methods work better when constraint matrix is sparse. Similarly, it is ...
0
votes
1answer
66 views

Inequalities with matrices

For a linear system of equations constrained by inequalities, is $ Ax \le b => y^TAx \le y^Tb $ acceptable? Or does that not generally hold. ($ y^T $ being the transpose of $y$).
1
vote
1answer
135 views

Totally Uni-modular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
0
votes
1answer
180 views

Positive semidefinite vector $\bar{x}$ as $\bar{x}>0 :=\bar{x} \lambda \bar{x}^{T}>0$?

$A \lambda A^{T} $ (quadratic form?) is used with matrices to check definiteness. What about with vectors? If I see conditions such as $\bar{x} > 0$, how can I know whether it means $\bar{x}_{i} ...
4
votes
1answer
1k views

Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions? Here's Wikipedia on doubly stochastic matrices.