All Questions
35 questions
1
vote
0
answers
255
views
Interpreting positive semidefinite matrix as a graph
Given any symmetric matrix $S \in \mathbb{R}^{n \times n}$, if $S \succeq 0$, is there a way to encode $S$ into a graph such that it takes into account the positive semidefinite constraint, and ...
- 275
2
votes
1
answer
133
views
Is the sum of the circulant matrix with a super upper triangular matrix diagonalizable?
By the circulant matrix $C$ in $M_n(\mathbb{R})$, we mean that
$$C=[e_n|e_1|\cdots|e_{n-1}]$$ where $e_1,\cdots,e_n$ are the standard basis vectors in $\mathbb{R}^n$. It is well-known that
$$C=\...
- 4,058
6
votes
1
answer
515
views
Non-diagonalizability of the adjacency matrix of a directed graph
Let $G$ be a directed graph with no multiple edges or loops and let $P_i$ be its vertices. Let $A$ be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$ if and only if there is a directed ...
- 4,058
2
votes
1
answer
407
views
A property of directed acyclic graph
Suppose $A \in \mathbb{R}^p$ is the adjacency matrix of a weighted directed acyclic graph $D$ with vertex set $\left\{v_{1}, v_{2}, \ldots, v_{p}\right\}$, i.e.
$$
a_{i j}=\left\{\begin{array}{lr}
...
2
votes
0
answers
72
views
How to delete the maximum number of rows of a Boolean matrix by maintaining the sum greater than zero in each column
I have a Boolean matrix (entries are "0" or "1"), which is not square. The sum over each row and each column is constant (but they can be two different values). I would like to ...
- 21
2
votes
2
answers
330
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A ...
- 25.4k
1
vote
0
answers
140
views
Adjacency matrix/tensor operations for graph sequences?
Consider a graph $G=(V,E)$. Its adjacency matrix $A$ is defined by $A_{u,v} = 1$ if $(u,v)\in E$, $0$ otherwise.
Consider a vector $x$ that associates a value $x_v$ to each vertex of $G$. Consider the ...
- 1,444
0
votes
0
answers
425
views
Linear independence of vectors in Graph Theory
I have poste this question on StackExchange but there were no takers - would I be luckier on this site?
Most of this is well known, so let me just restate the corresponding Math:
Given a connected, ...
- 419
13
votes
0
answers
237
views
A Dynkin type classification result in linear algebra
Let $G$ be a finite directed acyclic graph. The Cartan matrix $C_G=C$ of $G$ is defined as the matrix with rows and colums indexed by the vertices of $G$ and $c_{i,j}$ counts the number of paths from $...
- 26.5k
7
votes
0
answers
177
views
Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?
Let $A$ be a $2n$-by-$2n$ matrix with entries in
$\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal
matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$
has rank $\...
- 20.2k
1
vote
1
answer
60
views
Rank and edges in a combinatorial graph?
Fix a $d\in\mathbb N$ and consider the matrix $M\in\{0,1\}^{2^d\times d}$ of all $0/1$ vectors of length $d$. Consider the matrix $G\in\{0,1\}^{n\times n}$ whose $ij$ the entry is $0$ if inner product ...
- 13.9k
0
votes
1
answer
154
views
Energy of a symmetric matrix with $0$, $1$ or $-1$ entries
I have a symmetric matrix with entries $0$, $1$ or $-1$ which appeared in my works in graph theory (the diagonal entries are all zero). I need a good upper bound for the energy of this matrix; i.e. "...
- 351
5
votes
1
answer
425
views
Determining the primitive order of a binary matrix
Let ${\bf A}_n$ be an $2n \times 2n$ matrix that is defined as follows
$$
{\bf A}_n=\left(
\begin{array}{c}
0&0&\cdots&0&0&0&0&1&1\\
0&0&\cdots&0&0&...
- 313
2
votes
0
answers
203
views
Space of change of basis matrices between two similar matrices - how to reduce it with additional tests?
Assume we have two real symmetric $n\times n$ matrices: $A, B$. We can easily test their similarity: $\textrm{Tr}(A^k)=\textrm{Tr}(B^k)$ for $k=1..n$. In this case both can be rotated to the same ...
- 171
7
votes
1
answer
386
views
Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?
Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent:
The all-one vector $j$ is contained in the conic hull of $col(A)$.
...
- 81
1
vote
1
answer
123
views
Walks of odd Lengths in a Matrix
Consider the following matrix
$$
A=\left[
\begin {array}{cccc}
1&1&0&0\\ 0&0&1&0\\ 0&0&1&1\\ 1&0&0&0
\end {array}
\right].
$$
Assume that $B=A^k$ ...
- 211
5
votes
1
answer
382
views
Is it possible to compute a valid Laplacian matrix from an effective resistance matrix?
I am wondering whether it is possible to retrieve a node-admittance matrix $G$ (also called Laplacian matrix) in a purely resistive network composed of nets $\{1, \dots, i, \dots, j, \dots, n\}$, from ...
7
votes
1
answer
641
views
Lower bound on the eigenvalues of the Laplacian
I am looking for a graph for which $2 d_{i} < \mu_{i}$, for some index $i$, where $\mu_{1} \leq \mu_{2} \leq \dots\leq \mu_{n}$ are the eigenvalues of the Laplacian matrix $L(G)$ and $d_{1} \leq d_{...
- 123
2
votes
1
answer
1k
views
What does the basis of the null space of the constraint matrix of a flow problem look like?
Consider a directed graph $G=(V,\mathbb{A})$ and a set of flow constraints of the following form:
$$ \sum_{(u,v)\in\mathbb{A}}x_{u,v} - \sum_{(v,u)\in \mathbb{A}}x_{v,u} = 0 \forall v \in V$$
...
- 31
4
votes
0
answers
149
views
Zero diagonal nonsymmetric block checkerboard matrix: orbits and numerical ranges
Let $A \in \mathbb{R}^{m \times m}$ be a nonsymmetric zero diagonal matrix with a zero/non-zero pattern which is symmetric and persymmetric (i.e. symmetric in the northeast-to-southwest diagonal).
If ...
- 323
1
vote
0
answers
43
views
Is $L'L_\text{in}+L_\text{in}'L$ positive semi-definite?
Assume that $A$ is the adjacency matrix of a strongly connected directed graph, that is, $A$ is non-negative and irreducible. Let $$L_\text{in}=D_\text{in}-A',\;L=D_\text{in}-A'+D_\text{out}-A$$ where ...
- 11
2
votes
0
answers
956
views
The (minimum) rank of a relation
$\DeclareMathOperator{\rk}{rk}$
For an integer $n\ge 1$, let $\mathcal R_n$ denote the set of all reflexive binary relations on $[n]$. I define the rank of a relation $R\in\mathcal R_n$ to be the ...
- 23k
2
votes
1
answer
449
views
Extracting a full rank matrix from a 0-1 matrix
If $A$ is a $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$. If ever possible, what would be an efficient way of extracting a full rank $k\!\times\!k$ sub-matrix of $A$ by removing columns and rows of ...
- 23
0
votes
1
answer
229
views
Reference request: Strong Connectivity and the Incidence Matrix
Question: What would be a good reference for characterizations of strong connectivity of a digraph in terms of its incidence matrix?
Details: Consider a digraph $(V, E)$ with vertex set
$$V = \{v_1,...
- 123
7
votes
0
answers
335
views
Does this inequality always hold?
Denote the adjacency matrix of a given undirected graph by $g$. It is an $n$-by-$n$ symmetric Boolean matrix with elements on the diagonal to be zero ($n\geq 3$). Let $g_{12}=g_{21}=g_{13}=g_{31}=1$ ...
- 79
0
votes
1
answer
204
views
Are these particular kinds of matrices well known?
Given two positive integers $n$ and $a \leq \frac{n}{2}$ consider a $n \times n$ matrix $A$ such that,
all the diagonal entries are either $a$ or $a+1$
all the non-zero off-diagonal entries are $\pm ...
- 1,893
1
vote
0
answers
459
views
How to restructure adjacency matrix $A$ from shortest distance matrix $B$ in Network topology inference
An undirected graph with $n$ nodes could be referred to as an adjacency matrix $A$. $A=[a_{ij}]_{n×n}$ with $a_{ij}=a_{ji}=1$ standing for there being an edge between node $i$ and node $j$, and no ...
- 287
3
votes
1
answer
166
views
The spectral radius of a modified graph
Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.
This situation has many different names: $G$ is called the cone or the ...
- 6,962
5
votes
1
answer
706
views
What is the largest possible operator norm of a sparse (0,1)-matrix?
Inspired by this question, I was wondering about the following problem:
Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does ...
- 7,633
-1
votes
1
answer
492
views
Upper bound on iterations count for power iteration algorithm
I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out ...
- 89
3
votes
0
answers
1k
views
Matrix Operations Preserving Hurwitz Stability
I begin with terminology I use in the question. A real square matrix $A$ is
negative-stable if for every eigenvalue $\lambda$ of $A$, ${\mathrm{Re}}(\lambda) < 0$;
$\ast$-negative-stable if for ...
- 105
2
votes
2
answers
1k
views
Positive semidefinite decomposition, Laplacian eigenvalues, and the oriented incidence matrix
Suppose $A\in\mathbb{C}^{n\times n}$ is Hermitian and positive semidefinite with some decomposition $A=BB^*$, where $B=(b_{ij})\in\mathbb{C}^{n\times m}$ (not necessarily the Cholesky decomposition). ...
- 475
2
votes
2
answers
390
views
Ax=0, estimate min(Hamming(x)) ? Equivalently: Bipartite graph. How to find (estimate) minimal number of vertices1 which are connected with EVEN number of vertices2 ? Equivalently: estimate minimal weight of error correcting code ?
Consider system of linear equations Ax=0 over $F_2$ (field with two elements {0,1}).
Where number of variables is bigger than equations - so we have many solutions $x$.
Question How to estimate ...
- 24.8k
2
votes
2
answers
819
views
Computing the multiplicity of an eigenvalue of a 0-1 symmetric matrix...
When we want to compute the multiplicity of an eigenvalue of a 0-1 symmetric matrix (viewed as the adjacency matrix of an undirected regular graph), we commonly resort to the know lemma of Feit and ...
21
votes
5
answers
2k
views
The middle eigenvalues of an undirected graph
Let $ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_{2n} $
be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any work or references ...
- 784