Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...