0
votes
0answers
9 views

How is this a substitution? Linear algebra transformation matrix misunderstanding

I found the following matrix equation in '3D Surveillance System Using Multiple Cameras', (authors: Ajay Kumar Mishra, Bingbing Ni, Stefan Winkler, Ashraf Kassima) (link here): I don't follow the ...
0
votes
1answer
44 views

Unique least square solutions

There is a theorem in my book that states: If $A$ is $m\times n$, then the equation $Ax = b$ has a unique least square solution for each $b$ in $\mathbb{R}^m$. But can we find a counter-example to ...
0
votes
0answers
2 views

How can I apply a median filter directly to a time-varying rotation matrix?

I need MatLab script which would take a series of rotation matrices (referring to an actual physical object's orientation) and apply median filter to it to eliminate speckle noise from it. The way ...
0
votes
0answers
40 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
0
votes
0answers
27 views

resources about sparse global constrainted optimization

Please recommend a good resources (books/articles/software) about sparse global constrained optimization?
1
vote
0answers
27 views

How to find the rank of a toeplitz matrix?

Is there any trick to compute or estimate the rank of a toeplitz matrix ? Or is this still unknown for a general toeplitz matrix ?
2
votes
3answers
52 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
32 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
31 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
19 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
25 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
27 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
27 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
66 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
61 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
22 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
32 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
67 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
40 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
128 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
39 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
72 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
40 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
18 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
46 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
40 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
48 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
50 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
22 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
118 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
64 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
34 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
133 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
57 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
25 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
33 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
49 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
42 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
21 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
39 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 ...