Questions about the properties of vector spaces and linear transformations, including linear systems in general.
1
vote
2answers
44 views
Spectral decomposition of a combinatorial matrix/Random walks on $s$-sets
$\newcommand{\Z}{\mathbb{Z}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\la}{\lambda}
\newcommand{\1}{\mathbf{1}}
\newcommand{\R}{\mathbb{R}}$
Take any $n\in[3;\infty]$. Here and in what follows, $[k;\...
1
vote
0answers
99 views
Matrix rescaling increases lowest eigenvalue?
Consider the set $\mathbf{N}:=\left\{1,2,....,N \right\}$ and let $$\mathbf M:=\left\{ M_i; M_i \subset \mathbf N \text{ such that } \left\lvert M_i \right\rvert=2 \text{ or }\left\lvert M_i \right\...
9
votes
1answer
501 views
Relation between the Axiom of Choice and a the existence of a hyperplane not containing a vector
In a lot of problems in linear one uses the existence, for each $E$ vectorial space over a field $k$ , and each $x\in E$, of a Hyperplane $H$ such that $E=k\cdot x \oplus H$ (Let us denote $\mathcal{P}...
0
votes
0answers
17 views
Can we build the simplex Tableau from a graphical point (vertex)?
Everything is in the title, starting from a vertex in 2D dimension, can we continue the simplex method from there, using the vertex coordinates in the simplex tableau ?
Thanks a lot for your time
6
votes
1answer
156 views
Is this bound uniform in $N$?
I encountered this small combinatorial problem and do not quite know how to solve it:
Consider a set $\mathbf N:=\left\{1,2,....,N \right\}.$ This set has $\binom{N}{2}$ many subsets of cardinality $...
2
votes
0answers
51 views
Order relation between cohomology groups
We have $\mathbb{Q}$-graded finite dimensional vector space $V=\bigoplus_{i=0}^{n}V_{i}$ and following cochain complex
$$0\rightarrow V_{0}\xrightarrow[]{d_{0}} V_{1}\xrightarrow[]{d_{1}}\ldots\...
2
votes
1answer
59 views
On submatrices: size bound
Let $M$ be a generic $2n\times 2n$ matrix and fix $k\leq n$.
Suppose $\mathcal{F}$ is a family of submatrices under the conditions that $A\in\mathcal{F}$ provided
(a) $A$ is a $k\times k$ ...
3
votes
0answers
66 views
Sparsest similar matrix
Given a square matrix A (say with complex entries), which is the sparsest matrix which is similar to A?
I guess it has to be its Jordan normal form but I am not sure.
Remarks:
A matrix is sparser ...
1
vote
1answer
64 views
Closed Form Solution for Optimization Problem over the Space of Rigid Transforms
Is there a closed form solution to this constrained optimization problem:
\begin{equation}
\min_{R \in SO(3),\, \mathbf t \in \mathbb R^3} = \sum_{i = 1}^N \| M_i(R \mathbf p_i + \mathbf t) \|^2,
\...
3
votes
1answer
161 views
Can we classify the general linear maps such that for a fixed matrix $A \in M_n(\mathbb R)$ the conjuagation action fixes the first column?
Let $A \in GL_n(\mathbb R)$ be fixed. Let us consider the conjugation action by $G \in GL_n(\mathbb R)$, i.e., $G^{-1}AG$. I would like to see a way to identify the matrices such that the action fixes ...
4
votes
1answer
146 views
Intuitive proof of Golden-Thompson inequality
Sutter et al. [1] in their paper "Multivariate Trace Inequalities" give an intuitive proof of the following Golden-Thompson inequality:
For any hermitian matrices $A,B$:
$$
\text{tr}(\exp{(A+B)}) \...
-1
votes
0answers
52 views
Obtaining a Relation Between Positive Matrices
Consider $n \times n$ non-negative binary matrices
${\bf A}_i$ with $1\leq i \leq m$ over $\mathbb{R}$.
Assume that $1\leq k \leq n$ is selected as a fixed number.
Suppose that a subset of size $k$...
8
votes
3answers
242 views
Matrix determinant inequality proof without using information theory
Let $A$ be a $k \times n$ orthogonal matrix; i.e., $AA^T = I_{k \times k}$. For $1 \leq j \leq n$, let the squared norm of the $j$-th column of $A$ be denoted by $\alpha_j^2$; i.e.,
$$\sum_{i=1}^k a_{...
-2
votes
1answer
125 views
sum of positive definite matrix
sum of positive definite matrix $A+B $is positive definite. I want to look at the spectrum of $C=A+B$
can we say the ith largest eigenvalue of $C$ is no less than the ith largest eigenvalue of $A$ i....
0
votes
0answers
67 views
How to understand the span of a matrix? [closed]
https://people.eecs.berkeley.edu/~brecht/cs294docs/week7/12.candes.recht.pdf
In the section 3.3 of the paper above, the author explains the span of matrices:
To apply our results to recovering low-...
6
votes
0answers
75 views
Geometric mean of three or more positive definite matrices
The geometric mean of two positive definite (Hermitian) matrices of same size is defined by $$A\natural B := A^{1/2}(A^{-1/2}BA^{-1/2})^{1/2}A^{1/2},$$equivalently,
$$A\natural B =(BA^{-1})^{1/2}A=A(A^...
2
votes
0answers
33 views
Is every stable matrix orthogonally similar to a $D$-skew-symmetric matrix?
Let $\mathrm{diag}(A)$ denote the diagonal matrix with diagonal entries of $A\in\mathbb{R}^{n\times n}$ and let $\succeq$ denote the standard partial order in the cone of (symmetric) positive definite ...
1
vote
1answer
180 views
fiber of a map into Grassmanian
Suppose $R\subset K=K_0\supset K_1\supset K_2\supset...\supset K_{n-1}\supset K_n=\{0\}$ are all vector spaces with $\dim R\cap K_i=r_i$ where $r_i$ are some fixed numbers. Suppose $O\subset Gr(r_0,\...
2
votes
2answers
234 views
Laplacian of an infinite graph and connected components
For a finite graph with undirected, unweighted edges, a well-known result is that the dimension of the null space of the Laplacian matrix gives the number of connected components. Does this result ...
15
votes
3answers
541 views
$\sup \left\| A x + B y\right\|_2$ subject to $\left\|x\right\|_2 = \left\|y\right\|_2 = 1$
I'm interested in
$$\sup_{x, y} \left\| A x + B y\right\|_2$$ subject to
$$\left\|x\right\|_2 = \left\|y\right\|_2 = 1$$
where $A$, $B$ and $x$, $y$ are real matrices and vectors, respectively, of ...
0
votes
0answers
20 views
Kronecker sum matrix for a singular matrix pencil
The Kronecker sum of two matrices $A \in \mathbb{R^{n \times n}}$ and $B \in \mathbb{R^{m \times m}}$ is defined by the matrix.
$$A \oplus B = A \otimes I_m + I_n \otimes B \in \mathbb{R^{mn \...
0
votes
1answer
72 views
How eigenvalue perturbation affects back to the original matrix?
Both "eigenvalue perturbation" and "matrix perturbation" seems to study this scenario that given a matrix $A$, if we add something to it like $\tilde{A} = A+E$, how will the eigenvalues of $\tilde{A}$ ...
7
votes
1answer
137 views
How should I think about the module of coinvariants of a $G$-module?
Let $G$ be a group, $M$ a $G$-module, then the group of coinvariants is the module $M_G := M/I_GM$, where $I_G$ is the kernel of the augmentation map $\epsilon : \mathbb{Z}G\rightarrow \mathbb{Z}$.
...
6
votes
0answers
151 views
A binomial determinant formula: a new variant
In a previous MO question, the OP asks a proof for $\det_{1\leq i,j\leq n}\left(\binom{i}{2j}+\binom{-i}{2j}\right)=1$. Subsequently, Gjergji Zaimi generalized the problem to
$$\det_{1\le i,j\le n}\...
3
votes
1answer
220 views
Is there any Menelaus-type theorem for polynomials?
Consider $n+3$ polynomials of degree $n$, say $P_1(x) , ... P_{n+3}(x)$.
In addition, consider that there are distinct (it is not necessary that all of them be distinct) numbers $x_{ij}$ for $1 \...
2
votes
1answer
95 views
Eigenvalues of A^T D A for positive A and diagonal D
Suppose I have a diagonal matrix $D$ whose entries are bounded in absolute value. I also have a matrix $A$ that is positive (entry-wise, so $A_{ij} > 0\ \forall\ i,j$): one can assume that the ...
7
votes
1answer
169 views
The determinant of a $4\times4$ matrix associated to some specific polynomial as follow
Let $f\in \mathbb{R}[x_1,x_2,x_3,x_4]$ defined by
$$f_a(x_1,x_2,x_3,x_4)=\prod_{1\leqslant i<j\leqslant4}(x_i-x_j)^{2a_{ij}}$$
where $a=(a_{12},a_{13},a_{14},a_{23},a_{24},a_{34})\in \mathbb{N}^6$.
...
0
votes
0answers
39 views
What can we say about the dominant Generalized eigen vector of two matrices A and B if the dominant eigen vector of A and B are known?
I have the following problem: $\bf{a} = V_{max}(A,B)$, where $V_{max}$ refers to the dominant generalized eigen vector solution and A, B are two $N \times N$ matrices (full rank). Suppose i know the ...
0
votes
0answers
109 views
Existence of an “almost” skew-symmetric matrix
Let $A\in\mathbb{R}^{3\times 3}$ be a matrix of the form
$$
A=\begin{bmatrix}a_{11} & a_{12} & a_{13} \\ -a_{12} & a_{22} & a_{23} \\ -a_{13} & -a_{23} & a_{33} \end{bmatrix}
$...
5
votes
0answers
139 views
Can we represent partitions by mutually parallel lines in the plane?
Lately I have become interested in the following idea: Suppose $n$ is a positive integer and $[n]=\{1,2,3,...,n\}$. Suppose we have 3 distinct partitions $b$, $g$, and $r$ of $[n]$. Assume that the ...
-1
votes
1answer
131 views
Matrix Tic Tac Toe
So we have a 3x3 matrix and two players, a player that only puts in ones and a player that only puts in zeros. A coin flip is used to decide which player goes first. The first move is always to fill ...
5
votes
0answers
103 views
A nowhere-zero point in a linear mapping conjecture
I found a very interesting problem in the Open Problem Garden, which I am surprised is not as well-known as I would think it would be:
Prove that If $p>3$ is prime and $A$ is an invertible $n \...
1
vote
1answer
84 views
Upper Bounds on the Largest Eigenvalue of Jacobi Matrices
Suppose I have a symmetric tridiagonal (Jacobi) matrix in the following form:
$ \begin{pmatrix}
1 & a_{1} & 0 & ... & 0 \\\
a_{1} & 1 & a_{2} & & ... \\\
0 & a_{...
0
votes
0answers
38 views
Is there a formula for computing the parity of a sequence with discrete alphabet?
Suppose we have a sequence of number, whose alphabet is chosen from a discrete set such as (0,1,2). An example of such sequence is 0210122. Now I would like to determine if it is an odd permutation ...
2
votes
0answers
109 views
Motivation/intution behind using linear algebra in these combinatorics problems
What is the motivation behind using linear algebra in these three problems ?
A pair $(m,n)$ is called nice if there is a directed graph with (self edge are allowed, but multiple edge are not allowed)...
8
votes
4answers
646 views
How does the parity of $n$ affect the properties of $\mathbb{R}^n$? [closed]
Does the parity of the dimension of $\mathbb{R}^n$ affect its structure/properties? As in, does it make a difference if $n$ is even or odd?
2
votes
0answers
59 views
convex approximation for a non convex function
Consider the function
$f\left( {{x_1},...,{x_M},{y_1},...,{y_N}} \right) = \left( {\sum\limits_{j = 1}^M {{\alpha _j}{x_j}} } \right)\left( {{e^{ - \sum\limits_{i = 1}^N {{\beta _i}{y_i}} }}} \right)$...
2
votes
0answers
51 views
Determinant of a rank r perturbation
In the following paper:
Restricted Rank Modification of the Symmetric Eigenvalue Problem: Theoretical Considerations
on page 79, Golub et al. have the following set of equations:
$f(\lambda) = \...
2
votes
0answers
99 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 ...
1
vote
2answers
103 views
A “positive diagonal plus skew-symmetric” matrix decomposition
Let $A\in\mathbb{R}^{n\times n}$ be a diagonalizable matrix with real and strictly positive eigenvalues (note that $A$ is not required to be symmetric).
My question. Do there exist an orthogonal ...
7
votes
0answers
79 views
Volume of a neighborhood of singular matrices
Suppose we take the set of all $n\times n$ real matrices with entries in $[0,1]$ in Euclidean space. Let $N_\epsilon$ be the $\epsilon$ neighborhood of the set of all singular matrices in this space, ...
5
votes
1answer
112 views
On the linear factors of a polynomial obtained from the determinant of a matrix whose entries are related to Binomial expansion
Consider the polynomial ring $R=\mathbb C[x,y]$.
Consider the matrix $A=\begin{pmatrix} x^5+y^5&5x^5&10x^5&10x^5&5x^5\\5y^5&x^5+y^5 &5x^5&10x^5&10x^5 \\10y^5&5y^5&...
2
votes
0answers
94 views
eigenvalues of a square block matrix
How can we show that there are not defective eigenvalues for this square block matrix of dimension $2d \times 2d $: \begin{bmatrix}
A&B\\-B& 0
\end{bmatrix}
where A, B are real matrices, $A =\...
-3
votes
1answer
86 views
connected set of sum of upper semi continuous function [closed]
Let $C(X)$:space of continuous functions on a compact space.Topology $C(X)$ is generated by sup-norm($||T||=sup_{v}\frac{||T(v)||}{||v||}$).
Consider $f$ and $g :C(X)\rightarrow \mathbb{R}$ are upper ...
5
votes
1answer
124 views
Hilbert representation of a bilinear form
Let $\sigma:\mathbb{R}^n\times \mathbb{R}^n\to \mathbb{R}$ be a bilinear symmetric form which is non-degenerate in the sense that for every $0\neq u\in \mathbb{R}^n$ there is $v\in \mathbb{R}^n$ with $...
2
votes
1answer
52 views
Separation of two pointed polyhedral cones using hyperplanes generated by facets
Let $C_1$ and $C_2$ two pointed (that is, with vertex in $0$) polyhedral cones in $\mathbb{R}^n$ with $\dim(C_1)=\dim(C_2)=n$. If
$$\mbox{relative interior}(C_1)\cap \mbox{relative interior}(C_2)=\...
8
votes
1answer
112 views
Is the lattice generated by finitely many subspaces in a finite-dimensional vector space finite?
Let $V$ be a finite-dimensional vector space, let $U_1,\dots,U_n$ be subspaces, and let $L$ be the lattice they generate; namely, the smallest collection of subspaces containing the $U_i$ and closed ...
12
votes
0answers
265 views
Cardinality vs. isomorphism type of vector spaces without choice
One of the classical uses of the existence of bases of vector spaces (which is equivalent to the axiom of choice) is the following theorem:
If $V$ is an infinite vector space over a field $F$, and $...
0
votes
0answers
29 views
Vertices of intersection of affine subspace and a cube
Let $A\in\{0,1\}^{n\times n}, b\in\{0,1\}^n$.
Statement: Every vertex $v$ of the polyhedron defined by $\{x\in[0,1]^n|Ax=b\}$ satisfies $v\in\{0,\frac 1 n,\frac 2 n,\dots,\frac {n-1} n, 1\}^n$.
Is ...
2
votes
0answers
166 views
A parametrization of stable matrices
Let $A\in\mathbb{R}^{n\times n}$ be a diagonalizable matrix with real and strictly negative eigenvalues. Furthermore, suppose that $\mathrm{tr}(A)=-1$.
My question. I'm wondering whether it is ...
