All Questions
8 questions
1
vote
1
answer
165
views
Combinatorial graph optimization problem on integer adjacency matrices
We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers.
Let $z_{i,j}:=\frac{M_{i,j}}{M_{i,j}+\sum_{k\neq i,j}\min(M_{i,k},M_{k,j})}$ for all $1\le i<j \le n$, and
$z:=\...
- 1,677
0
votes
1
answer
134
views
Finding the minimum sum of a subset of entries of a given matrix with combinatorial constraints
Given a matrix $M\in\mathbb{N}^{n\times n}$, let $Z$ be the set of all the $M$'s entry subsets $S$ such that (i) no two entries of $S$ are on the same row or column of $M$ and (ii) $|S|=n$. Clearly we ...
- 1,677
2
votes
1
answer
367
views
The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero
Given an $n\times n$ matrix $A$, whose elements are over $GF\left(2\right)$ and all diagonal elements are $1$. There are $m\ (m\leq n^2-n)$ non-zero off-diagonal elements in $A$. If we are allowed to ...
- 21
5
votes
2
answers
252
views
Factoring a positive semidefinite matrix into binary matrices
This question is motivated by a research problem I recently encountered. Consider two sets of random variables $\mathbf{X}$ and $\mathbf{Y}$, where $\mathbf{Y}$ can be expressed as a linear ...
- 303
2
votes
1
answer
130
views
Maximum rank in a class of $0\,$-$1$ partitioned matrices satisfying combinatorial constraints
We are given a matrix $M \in \{0,1\}^{n\times n}$ satisfying the following property.
The rows and columns of $M$ can be partitioned into $k$ rowgroups and $k$ colgroups respectively, such that in ...
- 1,677
2
votes
1
answer
303
views
Submatrix with small sum of elements
Let $A$ be an $n \times n$ matrix, for which I know the size of the sum of all its entries. Now I want to select an $m \times m$-submatrix, whose sum of entries is as small as possible. Is there any ...
- 2,207
1
vote
0
answers
131
views
Lower bound on the value $\textbf{1}^Tx$ such as $Ax\geq b$
The problem may be formulated as follows:
We are given a set of $m$ positive numbers $\{b_1,...,b_m\}$ and a set of $n$ positive numbers $\{v_1,...,v_n\}$. We have $v_j\leq K$, $j=1,...,n$, for a ...
- 123
1
vote
0
answers
204
views
Complexity of reordering a matrix which consists independent sub matrices
Introduction:
Given a matrix A of a $k$ regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$.
$A_x$ is the symmetric matrix of the graph $(G-x)$, ...
- 267