Questions about the properties of vector spaces and linear transformations, including linear systems in general.

learn more… | top users | synonyms

3
votes
1answer
137 views

About partial uniqueness of SVD

In order to prove non-uniqueness of singular vectors when a repeated singular value is present, the book (Trefethen-Bau, considered the most authotitative book on the subject), argues as follows: Let ...
3
votes
0answers
42 views

successive schur complements

If I have a large (e.g. 6000x6000), sparse, positive definite matrix $M$ (which may have individual entries everywhere, but most non-zero entries are on / around the diagional). Divide $M$ into blocks ...
5
votes
0answers
244 views

Symmetric matrices with $\rho(A)\gg\|A\|_\infty$

For a symmetric real matrix $A$, denote by $\rho(A)$ the spectral radius of $A$, and by $\sigma(A)$ the largest absolute row sum of $A$; that is, $\sigma(A)=\max_i \sum_j |a_{ij}|$, where $a_{ij}$ are ...
2
votes
0answers
150 views

Norm bound of a complex resolvent

A well known result by Varah states that if $A$ is a strictly diagonally dominant matrix of dimension $n$, then $\|A^{-1}\|_{\infty} \le \max_i\frac{1}{|a_{kk}|-\sum_{j \neq k}|a_{kj}|}$, where the ...
5
votes
1answer
122 views

Simultaneous Tridiagonalization of a given set of hermitian matrices?

I have a set of $N\times N$ hermitian matrices $A_i,~i=1,\dots,M$. Are there any results on the possibility of simultaneously tridiagonalizing them?
5
votes
2answers
308 views

How to check whether a matrix is completely positive or not?

The definition: cone of completely positive matrices $\mathcal{C}=\{\sum_{i=1}^kx_ix_i^T:x_i\in\mathbb{R}^n_+\ for \ i=1,2,...,k\}$. I just don't knwo how to check whether a matrix belongs to ...
3
votes
1answer
89 views

submatrix of a given size with maximum frobenius norm

Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
7
votes
0answers
101 views

When is a product of hyperbolic matrices hyperbolic?

Suppose $A_1,\ldots,A_n$ is a sequence of $2 \times 2$ complex matrices such that $| \det(A_j) | =1$ and $ | \mathrm{tr}(A_j) | > 2 $ for each $j$. What kinds of reasonable restrictions can one ...
1
vote
1answer
135 views

Distributing the Hodge map over the wedge product

Let $(V,\langle,\rangle)$ be a finite dimensional inner product space, $V^{\wedge}$ it exterior algebra, and $\ast$ the Hodge star arising from $\langle,\rangle$. Does there exist any formula to ...
0
votes
0answers
47 views

Compare full-rank probabilities of products of random matrices

Consider two matrices $C_1=A\times B_1$ and $C_2=A\times B_2$, where $A\in\mathbb{F}_q^{N\times K}$, $B_1\in\mathbb{F}_q^{K\times M}$ and $B_2\in\mathbb{F}_2^{K\times M}$; $M\leq N\leq K$. It is ...
0
votes
0answers
77 views

Complexity of turning a d-degree polynomial to 2-degree polynomial

For a very simple example, $(1+x)^4=x^4+4x^3+6x^2+4x+1$ is a 4 degree polynomial, and I want to change it to a 2-degree polynomial by add more variables, for this example, we can simply let $y=x^2$, ...
28
votes
0answers
786 views

a naive question about the second dual of a vector space

Let $K$ be a field. Are there non-scalar endomorphisms of the endofunctor $$ V\mapsto V^{**}/V $$ of the category of $K$-vector spaces? I asked a related question on Mathematics Stackexchange, but ...
3
votes
0answers
143 views

Is there such a matrix in $SO(n)$?

Given two $n$ dimensional positive definite matrices $A', B'$, is there a matrix $O \in SO(n)$ such that $A=O A', B=O B'$ and $$ \frac{A_{ij}}{\sqrt{A_{ii}A_{jj}}} = ...
5
votes
4answers
322 views

NP-hard problems in linear algebra and real analysis [closed]

I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent. I would thus like to collect in this thread a list of ...
3
votes
3answers
234 views

Square root of a complex matrix commuting with a given one

Assume two commuting $n\times n$ complex matrices $A$ and $B$ are given. Then it is in general false that if $C$ is a square root of $A$, i.e., if $C^2=A$, then $C$ commutes with $B$ (the simplest ...
0
votes
1answer
80 views

dual space of the quotient space of some locally convex topological space

I would like to a classical result about dual space. Let $E$ be a locally convex space and $F$ its closed linear subspace. If $E^{\ast}$ is the dual space of $E$, could some one affirm me that the ...
1
vote
0answers
65 views

What is the time complexity of approximated SVD

Full SVD, on an m*n matrix $A$, $[U,S,V] = svd(A)$, would cost $O(m^2n + mn^2 + n^3)$ time. But what is the time complexity if we only need the $k$ largest singular values, say, $[U_k,S_k,V_k] = ...
17
votes
1answer
252 views

Linear maps between arbitrarily chosen vectors of vector spaces $V$ and $W$

I recently came across this question: Is the axiom of choice needed to prove the following statement: Let $V, W$ be vector spaces, and suppose $V \neq \{0\}$. Let $v \in V$, $v \neq 0$, $w \in W$. ...
4
votes
1answer
196 views

The height of the Perron-Frobenius eigenvector

Does the height of a real symmetric matrix with non-negative entries control the height of its Perron-Frobenius eigenvector, under some reasonable definition of heights? Just as an example of what ...
2
votes
1answer
82 views

Existence of parametrizations of rational orthogonal matrices

I suppose that there are formulas which parametrize all the orthogonal matrices with rational coefficients. Does anyone know anything about it? And what are some publications that discuss this? ...
0
votes
0answers
75 views

Sparse matrix factorization of a rank deficient matrix by decomposition into linearly independent components

I've got a little conjecture I need to prove for a theoretical result related to causal Bayes net search with latent variables under sparsity constraints. If you're interested in the application ...
1
vote
1answer
96 views

Neighborhood overlap matrix for a bipartite graph

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap ...
2
votes
1answer
77 views

Known Results on Convexity of Numerical Range

Let $A_1,A_2,\dots,A_M$ be given $N\times N$ hermitian matrices. The numerical range is defined as the set \begin{align} \mathbb{S}=\{(u^HA_1u,\dots,u^HA_Mu)\in \mathbb{R}^M\mid u^Hu=1\} \end{align} ...
3
votes
1answer
143 views

A hyperplane inside another one

Let D be a divison ring, let V be a left vector space of over D, possibly infinite dimensional, and let F be the prime field of D. Is it true that every F-hyperplane of V contains a D-hyperplane of ...
6
votes
2answers
294 views

When are two subvarieties of matrices conjugate?

Let $X$ and $Y$ be two subvarieties of $n\times n$ matrices. My question is that is there any condition to guarantee that there exits some matrix $g$ such that $Y=g^{-1} X g$? If such $g$ exists, then ...
-1
votes
1answer
59 views

Dimension of some ideal in the group ring Z/p[Z/p]

Let I be the augmentation ideal of the group ring Z/p[Z/p] and I^n denotes the ideal generated by all possible products of n elements from I. Question: What is dimension of I^n as a vector subspace ...
0
votes
0answers
85 views

What are the properties of this linear operator?

Suppose $f(x)$ is a function which satisfies the following condition: $$f(x)=\sum_{k=0}^\infty G(2k)\frac{x^{2k}}{(2k)!}$$ Where the generating function $G(x)$ is a "natural" or "discrete-analytic" ...
3
votes
0answers
94 views

“Shifted” Vandermonde determinant is nonzero?

I have already posted this question at MSE here, but as it received a few upvotes, but no comments or answers I choose to cross-post it here. Let $P$ be a degree-two polynomial, with roots ...
6
votes
0answers
126 views

A variant of an Eventown problem for modulo a prime number

Consider the following problem, called the 'Eventown problem': In a town, residents can form different clubs. The town council establishes the following rules: 1) Every club must have an even ...
4
votes
0answers
145 views

Dimension of a commuting nilpotent variety

Fix $k$ an algebraically closed field, $n$ a natural number, and $\lambda=(\lambda_1,\ldots,\lambda_m)$ a partition of $n$. Let $A$ be any $n\times n$ nilpotent matrix with entries in $k$ whose ...
15
votes
5answers
2k views

Origin of exact sequences

I have seen exact sequences appearing a lot in algebraic texts with different purposes. But I've never seen names of the people associated with it. Also I don't understand what's so good about showing ...
1
vote
0answers
132 views

Bounding the norm of the Dirichlet kernel as a matrix function

Consider the Dirichlet kerel: $f(x) = 1+2\sum_{k=1}^{N}\cos(kx)$. Now, given a diagonalizable real matrix $A$, one can consider $f(A)$, using the standard notation of matrix functions. Namely, $f(A) ...
0
votes
0answers
79 views

The largest size of a boolean subgraph (a hypercube) of a given graph

Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...
7
votes
1answer
154 views

How much can I perturb a symmetric stochastic matrix and keep positive solutions?

Suppose $A$ is a symmetric stochastic $n \times n$ matrix with least eigenvalue $\lambda_n>0$. Consider real symmetric perturbations $\widehat{A}$. How large can I take $\epsilon$ such that ...
3
votes
1answer
194 views

What is the canonical form of real symmetric 2n\times 2n matrix under unitary congruence?

If $M$ is a $2n\times 2n$ real symmetric matrix, I would like to ask what could be its canonical form under unitary congruence. We view a unitary $n\times n$ matrix $U$ as a real $2n\times 2n$ matrix, ...
-2
votes
1answer
142 views

Solving a difficult equation for a variable?

I'm trying to obtain the maximum likelihood estimate of the parameters for a model I'm building. I have constants $\sigma$, $\mu$, and $q_0$; a boolean matrix $\alpha$; and vectors $A, \beta, r, d,$ ...
2
votes
0answers
192 views

Separating the eigenvalues of a Hermitian matrix with a special block structure

I have a square matrix $J \in \mathbb{C}^{2n \times 2n}$ where, $J=\begin{pmatrix} A&B \\\bar{B} & A \end{pmatrix}$ $A \in \mathbb{R}^{n \times n}$ and is ${\bf diagonal}$. $B \in ...
3
votes
0answers
73 views

What do we know about the generalized eigenvalue problem involving a projector?

Consider a matrix $A\in\mathbb{R}^{n\times n}$ and a projector $P\in\mathbb{R}^{n\times n}$. Are there results regarding the generalized eigenpairs $(v,\lambda)$ of the generalized eigenproblem ...
0
votes
0answers
50 views

Eigenvalues of a “Half-Kronecker ” Product

The Problem: Given a 2 by 2 matrix $C$(the matrix elements of C are given), and two other 2 by 2 matrices $A$ and $B$(the matrix elements of A and B are given). Now we can construct a new matrix ...
0
votes
0answers
46 views

Forming orthogonal bases in different orders

Let $\alpha_1, \dots, \alpha_n$ be unit vectors in some vector space $V = R^d$. For any permutation $\pi: [n] \rightarrow [n]$, we can form the Gram-Schmidt orthogonal bases $\beta_{\pi,1}, \dots, ...
2
votes
1answer
243 views

Matrix equation XAX=B where the solution must be diagonal [closed]

$$X_{solution}=\arg\min_X \|XAX-B|_F \quad\mathrm{subject\ to}$$ X is square and diagonal A is square and positive semi-definite B is square and positive semi-definite Any pointers or relevant ...
1
vote
0answers
174 views

An optimization problem on the sphere

Let $S$ be a sphere centered at origin in $\Bbb R^{2n}$ of radius $\sqrt{2n}$. Let $D$ be a diagonal matrix. Let $U$ be an orthogonal matrix. Let $r\in\Bbb Z_+$ be a fixed integer. Let vector ...
0
votes
0answers
85 views

Linear system with many solutions from a finite set

Basically I am looking for a linear system with many solutions from a finite set. Choose a finite set of rationals $S$ and fix positive integer $k$. Let $A$ be a linear system with $n$ variables ...
4
votes
2answers
204 views

Finding roots of a recursively given polynomial sequence / eigenvalues of an almost Toeplitz matix

I would like to find the roots of the polynomial sequence given by a recurrence relation as follows: $V_0(x) = 1-a^2$ $V_1(x) = 1-a^2 - x$ $V_{k \geq 2}(x) = (1+a^2 - x)V_{k-1}(x) - a^2V_{k-2}(x)$ ...
3
votes
1answer
109 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 ...
1
vote
2answers
115 views

Bound on smallest entry of inverse matrix

For a symmetric, invertible matrix $A=(a_{ij})\in \mathbb{R}^{n\times n}$ with (at least two) nonzero off-diagonal elements, is it possible to bound in absolute value the smallest entry of its inverse ...
10
votes
1answer
293 views

Hölder's inequality for matrices

I was wondering if the Hölder's inequality was true for matrix induced norms, i.e. if $$\|AB\|_1 \leq \|A\|_p\|B\|_q, \quad\forall p,q \in [1,\infty] \text{ s.t. } \tfrac{1}{p}+\tfrac{1}{q} = 1.$$ But ...
3
votes
1answer
185 views

Calculating a generalized inverse (Moore–Penrose pseudoinverse)

I am considering a graph with $n$ edges with the following nicely structured adjacency matrix: \begin{equation} A_n= \begin{pmatrix} 0 & 0 & 0 &\cdots & 0 & 0 & 1\\ 0 & 0 ...
1
vote
0answers
81 views

Dimension of $L(E,F)$

Let $E,F$ be two vector spaces over a field $k$. $L(E,F)$ is the $k$-vector space of linear maps $E \rightarrow F$. In ZFC, is there a functionnal relation between $dim(L(E,F))$ and ...
1
vote
2answers
101 views

Mixing Numerical Range and inner product

Let $\mathbf{A}$ and $\mathbf{b}$ be a symmetric $N\times N$ real matrix and $N\times 1$ real vector respectively. Then consider the set of points in $\mathbb{R}^2$ defined as \begin{align} ...