All Questions
14 questions with no upvoted or accepted answers
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
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
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
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
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
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
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
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
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
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
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
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
-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