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 & ...
2
votes
1answer
44 views

Positive definite martix

I understand the majority of this solution, it's just I don't understand why I have to use both $\epsilon_1 $ and $\epsilon_2 $ rather than just $\epsilon$. I understand that i'm working with ...
0
votes
2answers
33 views

Least Squares Solution Confusion

Say if I have an overdetermined system $A\vec x=\vec b$, I can use the normal equations $\implies$ $A^TA\vec x=A^T\vec b$. If I solve for $\vec x$ I will get a "solution" with an error. It says in ...
0
votes
0answers
33 views

Efficient Factorization for Family of Matrix Equations

I am looking for an efficient solution to the following problem $$ A+\lambda I = b \tag{1} $$ where $A\in\mathbf{S}^{n}$ is a symmetric matrix with nonzero eigenvalues, $b\in\mathbf{R}^n$ is fixed, ...
1
vote
0answers
25 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
1answer
33 views

Simplying linear equation to get quartic in q using Maple and then using Descarte’s rule of sign

Using the maple I am trying to get quardic in q from this big linear equation. Then use Descarte’s rule of signs to determine the number of positive roots. \begin{equation} ...
0
votes
1answer
27 views

Solve for a matrix in a linear equation

This is probably a really basic question, but we are stuck and the usual keyword lead to the normal "Solving linear equations with matrices"/Gaussian-elimination pages ... I have an equation $A X B + ...
2
votes
2answers
57 views

Determinant of an ill conditioned matrix

I have the following ill conditioned matrix. I want to find its determinant. How is it possible to calculate it without much error \begin{equation} \left[\begin{array}{cccccc} ...
0
votes
0answers
33 views

System of linrar equations and condition number

The relative error of the solution of a system of linear equation $Ax=b$, for any natural norm $\|\cdot\|$ is bounded by $$ \frac{1}{\| A\| \|A^{-1} \|} \frac{\|r\|}{\|b\|} \le \frac{\|e\|}{\|x\|} \le ...
0
votes
0answers
28 views

condition number of orthogonal matrix

Let $A\in M_n(\mathbb R)$ be an orthogonal matrix. Then: $cond (A) =1$. I tryed to use facts about the eigenvalues but is did not help. In 2-norm it is easy to prove it since $||A||_2 = \sqrt{\rho ...
0
votes
0answers
10 views

Spectral norm of a Hadamard product

Let $F$ be the $n\times n$ DFT matrix, i.e., $F_{i,j} = \exp\left(-\tfrac{2\pi(i-1)(j-1)}{n}\imath\right)$, for $1\le i,j\le n$ and $\imath =\sqrt{-1}$. Futhermore, let $\Vert \cdot\Vert$ and $\circ$ ...
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 ...
3
votes
0answers
47 views

Does anyone know any reference for this matrix?

For $n \geq 4$, $A$ is $(n-1) \times (n-1)$ tridiagonal block matrix $$A = n^2 \begin{bmatrix}B & -I & 0 & \cdots & \\-I & B & -I & 0 & \\ 0 & -I & B & -I ...
1
vote
1answer
41 views

Inverse of constant matrix plus diagonal matrix

Is there an efficient way to calculate the inverse of an NxN diagonal matrix plus a constant term? I am looking at N of around 40000. $\left[\begin{array}{cccc} a & b & \cdots & b\\ b ...
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
0answers
18 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...
1
vote
0answers
28 views

Influence of preconditioning on degenerate eigenvectors

I'm using a hierarchical decomposition of a sparse matrix $A$ as suggested here. I find that the method essentially finds eigenvectors using the QR algorithm. $A$ has some eigenvalues with ...
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
1answer
50 views

Efficient method for determining to the most positive eigenvalue of a matrix

I am trying to implement an algorithm that requires knowing the largest $\textbf{positive}$ eigenvalue of a $\textbf{real symmetric, non-sparse}$ matrix and the corresponding eigenvector. The actual ...
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 ...
1
vote
0answers
21 views

If symmetric matrix in a least-square deconvolution problem positive definite?

I want to apply Gauss-Seidel method in a least square deconvolution problem. The convolution of two vectors is written in: $h * x = z$. $$z(n) = \sum_{i=0}^{N-1}h(i)x(n-i)$$ It is a linear transform ...
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 ...
0
votes
2answers
36 views

Eigenvalues and eigenvectors of a matrix

We know that if $\lambda (\neq 0)$ is an eigenvalue of a matrix $A$ corresponding to eigenvector $X$, then $\dfrac{1}{\lambda}$ is an eigenvalue of $A^{-1}$. But whether the corresponding eigenvector ...
0
votes
0answers
18 views

Orthogonal polynomials induction proof

I tried writing this all out but cannot seem to get anything sensible. Basically I want to prove that assuming w(x) is the weight function of a Gram Schmidt orthogonalization process and w is an ...
0
votes
1answer
41 views

Is this Gram-Scmidt (or an application of) it?

I am given a $2\times 2$ matrix $$\left[ \begin{array}{ccc} a & 0 \\ 0 & b \\ \end{array} \right] $$ where $a,b \in \mathbb{R}$. I was told than an orthnormal basis for the colums of this ...
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 ...
3
votes
1answer
92 views

Prove $|\det A| \leq \prod_{j=1}^n ||a_j||$

Let's say A is a square n by n matrix. ||$x$||=$x^T x$ and x is a real n-column norm. How would you show this? I tried to use the QR factorization here in showing that ||$a_j$||=||$r_j$||, but ...
1
vote
2answers
122 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 $$ ...
3
votes
1answer
210 views

Numerical verification of solution.

I have the non-linear equation \begin{align} &\left( {x}^{2}-1 \right) \left( -\frac{1}{4}\left({\frac { \left( 4\,{x}^{3}+2\, ex \right) ^{2}}{ \left( {x}^{4}+e{x}^{2}+f \right) ...
1
vote
0answers
43 views

Numerical algorithm to solve quadratic eigenvalue problem.

Given the equation $$-4 \left(a^2+a (n-1) (2 t^2-1)\right) \left(\sum _{i=0}^n \alpha_i t^{2 i}\right)^2 \\ +\frac12 \left(\sum _{i=0}^n \alpha_i t^{2 i}\right) \left(t \left(8 a (t^2-1)+1\right) \sum ...
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
1answer
60 views

Proof that eigenvector corresponding to simple eigenvalue is continuous

Let $\lambda$ be a simple eigenvalue of $A \in L(C^n)$ and let $x$ be the corresponding eigenvector. Then for $E \in L(C^n)$, $A+E$ has an eigenvalue $\lambda(E)$ and an eigenvector $x(E)$ such that ...
0
votes
0answers
29 views

Kalman Filter Predict Update of LDL Decomposition of a Covariance Matrix

From the state predict equation: http://en.wikipedia.org/wiki/Kalman_filter# $$P_{n+1}=AP_nA^T + Q$$ Suppose the $LDL^{T}$ ( http://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition_2 ) ...
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
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
116 views

Check if the following gradient is correct

This question regards the verification of the gradient of a given function. Notation. Let $N, K \in \mathbb{N}_0$ be given (nonzero) integers, with $K > N$. Let $\mathbf{x} = [x_b \ y_b \ z_b]^T ...
0
votes
1answer
20 views

How to evaluate the accuracy for sparse linear system solver

I'm currently trying to do some experiments on linear solver. However, it's a little hard to get the sense of the numbers. For example, I know large condition number is bad, but how large is bad? ...
0
votes
0answers
27 views

Not enough memory for GMRES

After realizing that Gauss-Seidel is extremely slow for my simulation, i wanted to try GMRES and luckily found the C++ code here without diving into the theory. The size of the matrix in my case is ...
1
vote
2answers
49 views

Gauss-Seidel method convergence algorithm

From Wikipedia: The convergence properties of the Gauss–Seidel method are dependent on the matrix A. Namely, the procedure is known to converge if either: ...
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
44 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 ...
0
votes
1answer
44 views

Is this matrix guaranteed to be positive-definite?

(This question pertains to a larger model proposed in this SIGRAPH paper, but I've pulled out the pertinent question and generalized it.) Let's say I have two large matrices $M$ and $L ...
0
votes
1answer
26 views

Matrices in Linear Algebra

Let: $ u: R^2 --> R^3$ be defined by: $$ u(x,y)=(x+2y, 2x-y, 2x+ 3y)$$ Give the matrix $M[u]$ in the canonical base of its definition space. This question might seem sort of stupid, but it was ...
0
votes
0answers
35 views

Francis Algorithm (Implicit QR Algorithm)

In Numerical Analysis, we are touching upon QR and Francis Algorithm. I understand that for Francis's Algorithm, we reduce the matrix to its upper Hessenberg form using Householder transform. What I ...
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 ...
5
votes
1answer
28 views

proving a theorem of alternative

I've read the following exercise in my book: Let $A\in\mathbb R^{m\times n},b\in\mathbb R^m,c\in\mathbb R^n$. Then exactly one holds: $Ax=0,c^t\cdot x=1$ with $x\geq0$ has a solution $A^ty\geq c$ ...
2
votes
1answer
103 views

(A + D)x = b … efficiently!

let say we have $A$ to be symmetric positive-definite (SPD), moreover block tridiagonal Toeplitz matrix and $D$ is block diagonal SPD (both with full rank). Let say we know everything about $A$ and ...