1
vote
3answers
44 views

How to reverse matrix vector multiplication?

I'm using the simple matrix x vector multiplication below to calculate result. And now I wonder how can I calculate ...
1
vote
0answers
25 views

Iterative methods for solving a linear equation system

There are several methods known for solving a linear equation system Ax = b (like Jacobi or Gauss-Seidel) by iterating $x_{n+1}=Mx_n+c$ with a matrix M, for which some norm is smaller than 1. But ...
2
votes
1answer
30 views

A generalization of GMRES

In oder to solve $Ax=b$, GMRES method finds $x_n$ in the $k$-th Krylov subspace i.e.: $$K_n=span\{b,Ab,...,A^{n-1}\}$$ and we have the condition: minimize $\|r_n\|_2$, which $r_n=b-Ax_n$ Now we ...
1
vote
0answers
18 views

About reduction to Hessenberg matrix

I've read somewhere that Hessenberg decomposition is not unique unless the first column of $Q$ is given. i.e $Q^TAQ=H$ Then I read the algorithm of Arnoldi iteration and I found an amazing fact: ...
1
vote
0answers
23 views

Solving tridiagonal matrices where the top left element is zero

If I have a matrix like this: $$ \left[\begin{array}{rrrrrrrrr|r} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & ...
1
vote
0answers
26 views

When is the LU decomposition unique?

I want to find out when a matrix decomposition $A = LU $ (L lower and U upper matrix) is unique? Clearly, if $A$ is not invertible, there is no chance that this decomposition is unique. Hence, ...
0
votes
2answers
20 views

Finding a rotation matrix

I am looking for a rotation matrix such that $$ \operatorname{rot} \cdot \begin{pmatrix} -1 & 0 & 0 \\ 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{pmatrix} = ...
1
vote
1answer
26 views

Lipschitz continuity for generalized inverse matrix

Suppose $A$ and $B$ are full-rank and well-conditioned. Is Lipschitz continuity held for generalized inverse? $$\|A^+ - B^+\| \le \omega \|A-B\|,$$ for some $\omega > 0$, where the norm could ...
2
votes
1answer
65 views

Linear equation: $(A^\top A+B^\top B + D)x=c$ where $A,B$ are structured sparse and $D$ is diagonal.

Updated: the goal is to solve $(A^\top A+B^\top B + D)x=c$. Maybe it is not necessary to compute $(A^\top A+B^\top B + D)^{-1}$. Denote $e=(1,1,\ldots,1)^\top\in\mathbb{R}^n$ and ...
1
vote
1answer
39 views

Consistency of the system $AX=b$

In the concept of consistency (compatibility) of a matrix, when $b \in \mathbb R (A)$ we know for sure that the system is consistent or there may exists no solution for it? But when $b \notin \mathbb ...
1
vote
0answers
56 views

Newton's method for multidimensional functions

Can Newton's method be used to find the root of a function f : $\mathbb{R}^n\to\mathbb{R}^m$. Can anyone provide a proof for this? (I have checked the method of solving system of equations with ...
1
vote
0answers
18 views

Change in Singular Value Decomposition of a matrix on addition of a single row

Given that I know the svd decomposition of a matrix, is there any way to compute the svd decomposition of the matrix obtained by adding a single row to the original matrix? Is there any relation ...
0
votes
0answers
31 views

How to find a transformation matrix T?

(1.) Suppose there is matrix C of dimension "p by n" where p is less then n i.e. p I want to know is there any particular way exist to find transformation matrix T of dimension "n by n" such that ...
2
votes
1answer
65 views

Matrix Norm Inequalities and Linear Least Squares

I am working through one of my universities old QUALS and came across the following problem: Let $A,E\in \mathbb{C}^{m\times m}$. Suppose that $\sigma_\min>0$ is the smallest singular value of ...
0
votes
1answer
26 views

Matrix with constant row sum

It is well known (and shown several times on this site) that if we have a matrix so that each row sums to zero then the matrix must be singular. I am curious if the following partial converse is ...
1
vote
2answers
123 views

Trace minimization of a matrix

Suppose $S = \pmatrix{1&1\\ 1&0\\ 0&1}$, $W$ is a $3\times3$ covariance matrix, which could be regarded as fixed. I need to find a $2\times 3$ matrix $Q$ that minimizes $$ ...
1
vote
2answers
37 views

How to figure out the spectral radius of this matrix

$$A=\begin{array}{ccc} 0 & 1/2 & 0 & \cdots & 0 \\ 1/2 & 0 & 1/2 &\cdots& 0\\ 0 & 1/2 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots &\ddots ...
1
vote
1answer
53 views

Norm of Block Diagonal Matrix

Given a matrix $A \in R^{m \times n}$ with known upper bound on the operatornorm $\| A \|$ I want to find an upper bound for the operator norm of the square root of the following matrix that is given ...
1
vote
0answers
19 views

Algorithm for finding only the $k$-th singular vectors

I know that we have truncated SVD that can compute the first say $k$ largest singular values (and corresponding singular vectors). However, I'd like to know if there is an algorithm that can find only ...
1
vote
0answers
38 views

Best way to solve specific block-tridiagonal linear system (10000x10000 and larger)

To provide more context, this system came from energy balance equation on a mesh with (n,m) nodes in each direction. It's a linear system that looks like this (size of system in blocks n = 4, size of ...
0
votes
1answer
33 views

Induced Matrix Norm

I have trouble following a proof of the induced Norm $||\cdot||_1$ The proof can be found here: ...
0
votes
0answers
17 views

Maximal angle between kernel of rows of a matrix

Consider a matrix with 2 columns $$ \begin{pmatrix} a_1 & b_1 \\ a_2 & b_2 \\ a_3 & b_3 \\ \vdots & \vdots \end{pmatrix} . $$ To each row $(a_i \;\;\; b_i)$, one draws the kernel ...
2
votes
1answer
44 views

Least squares problem with orthonormality constraints

Given $y_1,\ldots,y_n\in \mathbb{R}$,$w\in \mathbb{R}^d$, and $x_1,\ldots x_n\in \mathbb{R}^D$, how do we solve the following optimization problem \begin{align} \min_A \sum_{i=1}^n (y_i-w^TA^Tx_i)^2\\ ...
1
vote
1answer
35 views

block matrix multiplication

If $A,B$ are $2 \times 2$ matrices of real or complex numbers, then $$AB = \left[ \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]\cdot \left[ \begin{array}{cc} b_{11} ...
2
votes
1answer
45 views

fast multiplication for a matrix and its transpose.

I know Strassen and other methods can achieve better than $O(n^3)$ for general square matrix multiplication. I am curious of the spacial case where the multiplication is between a $n*m$ matrix $A$ ...
2
votes
1answer
49 views

Spectral norm of symmetric matrices only with the diagonal, the first column, and the first row non-zero

Consider a real symmetric matrix $$\mathbf{M}=\left[\array{a_0&a_1&a_2&\cdots&a_n\\ a_1&b_1&0&\cdots&0\\ a_2&0& b_2&\cdots&0\\ \vdots &\vdots ...
1
vote
1answer
21 views

QR decomposition

Assuming that we have a QR decomposition of a matrix $A \in \mathbb{R}^{m \times n}$, $Q \in O(m)$ and $R \in \mathbb{R}^{m \times n}$ such that $A=QR$, where R is an upper triangular matrix. Now ...
3
votes
1answer
51 views

Linear Algebra quesion

$A^{-1} - \lambda A = B^{-1} - \lambda B - \alpha v v^T$ $A, B \in S^n_+$; $v \in R^n$; $\lambda, \alpha \in R_+$. Can we solve A in term of other variables?
2
votes
1answer
113 views

A Beautiful Determinant!

Find the determinant of the following matrix in the terms of $a_1,a_2,\cdots,a_n$ explicitly, $$ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_n\\ a_2 & a_3 & a_4 & \cdots ...
1
vote
0answers
31 views

Gerschgorin Theorem singularity proof

I know how to prove the Gerschgorin Theorem but how exactly would one show that there are no values of $\mu$ s.t. $\mu<0$ for which $A-\mu B$ is singular where $$ A= \begin{bmatrix} ...
2
votes
1answer
63 views

Non-Orthogonal Eigenvectors and Computation?

Say for a real, rectangular matrix $X$ and a s.p.s.d matrix $Q$ we maximize or minimize $Tr(X^TQX)$ under the constraint $Tr(X^TM) = 1$ for some fixed real matrix $M$. i) Would the columns of the ...
2
votes
1answer
33 views

Eigenvalue of (1-0) matrix

Assume I have 2 matrices, each of size nxn with only 1 and 0 as entries in both. (n>10) The first matrix (call it A) has each row summing up to 2 (ie: on each row, it has two "1" and n-2 "0"). It is ...
1
vote
2answers
124 views

Cholesky Decomposition for positive semidefinite separation

Cholesky decomposition is a common way to test positive semi definiteness of a symmetric matrix $A$. If the algorithm "goes wrong" trying to take a square root of a negative number, I know the matrix ...
0
votes
1answer
66 views

Householder matrix Uw acts as the identity on the subspace w

How can i show that a Householder matrix $U_w$ acts as the identity on the subspace $w$? and that it acts as a reflection on the one-dimensional subspace spanned by w; i.e., $U_w(x) = x$ if $x$ is ...
3
votes
1answer
53 views

Is there a faster way to calculate a pseudo-inverse of a matrix than using SVD that is as numerically stable as with SVD?

Is there a faster way to calculate a pseudo-inverse of a matrix than using SVD that is as numerically stable as using SVD?
1
vote
2answers
65 views

Exponential of a 3x3 lower bidiagonal matrix

I have a 3x3 matrix with non-zero entries ONLY along the main diagonal and the diagonal above. There are exactly two non zero diagonals in the matrix like this \begin{pmatrix} a & 0 & 0 \\ d ...
1
vote
1answer
24 views

Solving Ax = b where A is composed of diagonal blocks

I would like to solve the equation $Ax=b$ where $x\in\mathbb{R}^n$ and $A$ is of the form: $$A= \begin{bmatrix} D_1 & D_2 &D_3 \\ D_2 & D_4 & D_5 \\ D_3 & D_5 & D_6 ...
1
vote
1answer
30 views

Checksum Invariants for Matrix Inversion via Gaussian Elimination

In general, when solving $Ax=b$, we make the $[A|b]$ matrix and doing row operations to reduce the left hand side to an identity. It's painfully annoying to find mistakes in the process. Assuming we ...
2
votes
0answers
47 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
1
vote
2answers
47 views

Square Idempotent matrix: efficient algorithms for finding eigenvectors

Given a square idempotent $N \times N$ matrix $A$ with large $N$, and a priori knowledge of the rank $K$, what is the most efficient way to compute the $K$ eigenvectors corresponding to the $K$ ...
0
votes
1answer
35 views

matrix exponential and Spectral abscissa

Prove that $\lim_{t \rightarrow \infty} \|e^{tA}\| = 0$ if and only if $\alpha(A) < 0 $, where $\alpha$ is the Spectral abscissa, defined as $\max{Re(\lambda_i)}$. I tried to approach this ...
0
votes
1answer
20 views

Complexity of sparse back substitution

What is the complexity of sparse backsubstitution $Rx = b$, given $n$, the dimensions of dense $x$ and $b$ as well as of the sparse $R$ and $nnz$, the number of nonzero entries in $R$?
1
vote
1answer
43 views

Special Matrix 2-norm and F-norm Inequalities

This is a homework problem for my Numerical Linear Algebra course. It states the following: If A is an mxm nonsingular matrix, prove the following: (1)$\|A+(A^{*})^{-1}\| _{2} \ge 2$ ...
1
vote
2answers
38 views

Relation between condition number and perturbed matrix

Prove that if $A\vec{x} = \vec{b}$ and $(A+\delta{}A)(\vec{x}+\delta\vec{x}) = \vec{b}$, then $\dfrac{\|\delta\vec{x}\|/\|\vec{x}+\delta\vec{x}\|}{\|\delta{}A\|/\|A\|} \le \kappa{(A)}$, where ...
1
vote
4answers
143 views

How to tell if two matrices are equal up to a permutation

Given two real rectangular matrices A, B how can I tell if they are equal up to a permutation of their rows/column without trying all possible permutations? (This is closely related to the question I ...
1
vote
0answers
62 views

Algorithm to determine matrix equivalence

I'm a physicist who's not particularly good at linear algebra so please accept my apologies if this is standard textbook stuff that I'm just unaware of. I have two real rectangular matrices $A_{mxn} ...
1
vote
1answer
51 views

Inverse of a triangular matrix in a statistical problem

Can any one give to me idea how to solve this problem? Find the inverse of the triangular matrix T, where $ T =\left[ \begin{array}{ccc} I & J & J \\ 0 & I & J \\ 0 & 0 & I ...
0
votes
0answers
23 views

Matrix conditioning with one degree of freedom

Given a not so well conditioned, NxK, N>>K matrix A with a certain structure. I have just one degree of freedom: I can multiply each row with a different factor. In formula: $$ \mathbf{B} = ...
1
vote
2answers
127 views

Showing that $A=B+\alpha \cdot I$ is an invertible matrix

Let $B$ be a non-zero random $n\times n$ matrix generated using the matlab command $B=rand(n,n)$. I need to show that $A=B+\alpha \cdot I$ is an invertible matrix, where $\alpha=\|B\|_{\infty}$. I ...
0
votes
1answer
37 views

Inequality matrix norm

Let $A$ be an $n\times n$ random matrix $A=rand(n,n)$. Let $\alpha=max_{i,j}|a_{ij}|$ (i.e, $\alpha$ is the largest entry in $A$ in absolute value).I need to show that $\ \alpha < \| A \|_{2}$. ...