Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

4
votes
0answers
132 views

What does affine invariance mean in the context of the Newton's method?

The textbook Numerical Solution of Boundary Value Problems for Ordinary Differential Equations (by Ascher, Mattheij, and Russell) states on page 329: [W]e observe that Newton's method is affine ...
1
vote
1answer
38 views

Show that a positive definite (not necessarily symmetric) matrix induces a hyperellipse

Consider $A\in M_n(\mathbb{R})$ a positive definite matrix and a matrix $B\in M_{n \times p}(\mathbb{R})$, with $n\geq p$ and $rank(B)=p$. i) Show that $C=B^TAB$ is positive definite. ii) Show that ...
1
vote
1answer
40 views

Problem with Broyden update: Divide by a matrix?

I am implementing a maximum likelihood method (the EM algorithm) for which I'm using Broyden's method at each iteration. Here is the formula: $\Delta A = \frac{(\Delta \theta - A ...
3
votes
1answer
121 views

Find desired root (based on certain constraints) while using Newton-Raphson method

My function is a vector of dimension 6, and on using Newton Raphson method, the solution usually converges to the nearest root. However, I know that my function has multiple roots (it's an Inverse ...
1
vote
0answers
404 views

Really confused about LU decomposition and Doolittle algorithm

I'm really confused about the Doolittle algorithm, so I need some help. At the end of the description at wikipedia, it says It is clear that in order for this algorithm to work, one needs to ...
1
vote
0answers
76 views

Question on the uniqueness of LU decomposition

Let $A \in \mathbb{K}^{n \times n}$ a matrix, and suppose that we can run the Gaussian elimination on $A$ without row or column interchange, so there exist the $LU$ decomposition of $A$. We define ...
7
votes
1answer
86 views

Singularity of a positive linear combination of rank one matrices

Given a set of rank one matrices $A_1,..,A_n$, we need to find out if there exists $x \in \mathbb R^n$ with $x\gg 0$ (i.e, positive) such that $$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + x_n A_n $$ ...
0
votes
0answers
158 views

QR method for Hessenberg matrices

In trying to implement the method, my approach is to use a reduction to Hessenberg form, and then to iterate using a QR method of Givens rotations. However, I am having trouble successfully ...
1
vote
1answer
42 views

Convergence of the LR algorithm for $2\times 2$ SPD matrices

I've been asked to prove that the following iterations converge to the eigenvalues of SPD $A_0 \in \mathbb{R}^{n \times n}$ $A_0 = \begin{bmatrix}a & b\\ b & c \end{bmatrix}$ with $a \geq ...
0
votes
1answer
196 views

efficient computation of Cholesky decomposition during tridiagonal matrix inverse

I have a symmetric, block tridiagonal matrix $A$. I am interested in computing the Cholesky decomposition of $A^{-1}$ (that is, I want to compute $R$, where $A^{-1}=RR^T$). I know how to compute the ...
0
votes
1answer
56 views

Relationship between eigenvectors of two matrices

Suppose I have matrix $A \in R^{2n \text{x} 2n} $ given by $X^{-1} diag(W - iY, W + iY) X$ and matrix $B \in C^{n \text{x} n}$ and $B = W + iY$. Let $v$ be an eigenvector of $A$. How can I relate ...
1
vote
1answer
74 views

Hessenberg reduction

Given $A \in \mathbb{R}^{nxn}$ and $z \in \mathbb{R}^n$, find orthogonal $Q$ such that $Q^TAQ$ is upper Hessenberg and $Q^Tz = \beta e_1$. My attempt so far, Individually I can find the Householder ...
1
vote
1answer
83 views

questions on polynomial Lagrange Interpolation of order $n$?

I ran in One Ex in my book when I‌ prepare for final exam on numerical method. how can help me how we solve such a problem? if $P(x)$ and $Q(x)$ be two polynomial Lagrange Interpolation of order $n$ ...
1
vote
2answers
31 views

solving given linear equation

So before you guys judge me, I honestly am so clueless with this so please bare with my dumb questions. I have been at this equation that I've been going for an hour now, $\frac{(3x-1)}{2} -2 = ...
3
votes
0answers
82 views

How do I apply this PDE as an image filter?

I'm trying to preprocess a height map image with a helmholtz-type equation as described in this paper. The equation is: $$ddx(h') + ddy(h') + y(h'-h) = 0$$ I solved for h and got: ...
0
votes
2answers
59 views

How to minimize $w^{T}Aw$?

$A$ is $n\times n$ matrix. Find a $w$ ( $n$-dimensional unit vector) which minimizes this function. By $w^{T}$, I mean $w$-transpose. I understand there would be non-linear optimization techniques ...
0
votes
2answers
37 views

Decomposition of a diagonal matrix into a product of particular matrices.

Could you tell me please, if it's possible to find a decomposition of a diagonal matrix $ 3 \times 3 $ : $ D ( \lambda_1 , \lambda_2 , \lambda_3 ) = \begin{pmatrix} \lambda_1 & 0 & 0 \\ 0 ...
2
votes
1answer
146 views

Properties shared by similar and unitary similar matrices.

We know that matrices $A$ and $B$ are similar if there exists an invertible matrix $P$ such that $A=PBP^{-1}$ and they are unitarily similar if $P$ is unitary ($PP^*=P^*P=I$). I want to know : What ...
2
votes
1answer
59 views

SVD and transpose of a skinny matrix

Show: If $\mathbf{A}\in\mathbb{R}^{M\times N}$ with $M\geq N$, then there exists a matrix $\mathbf{G}$ with orthonormal rows so that $\mathbf{A}^T=\mathbf{G}\mathbf{A}\mathbf{G}$. I'm pretty lost on ...
0
votes
1answer
207 views

Deducing a formula for multiplying a tri-diagonal symmetrical matrix with vectors

This is more like a math-programming problem, dealing with memory efficiency, but I thought it would be nice to expose it here. Let $A \in \mathbb{R}^{n \times n}$ be a tri-diagonal symmetrical ...
0
votes
1answer
561 views

PageRank (power iteration method) convergence rate?

I could not get my head around the idea that the second eigenvalue is the convergence rate. Since the matrix in this application is a Markov matrix (rows/columns sum to one), the largest eigenvalue ...
1
vote
1answer
194 views

How page rank relates to the power iteration method

I do not see how pageRank relates to the power method. Since for the pageRank we are looking for the steady stable state (vector) for a Markov (transition) matrix and the matrix has already an ...
4
votes
1answer
60 views

Laplacian solvers for inversion of large matrices?

I have a large matrix L of size 400,000 $\times $ 400,000 . I'm using this L matrix in the following way. Lin = L$^{-1}$ C = D - B * Lin * B'; B,D are of appropriate sizes. L matrix is ...
0
votes
2answers
203 views

Generalized formula for sum of products.

Q:The sum of all possible products of the first n natural numbers taken two by two is? I did not understand the question as it is.What exactly is being asked?I'd really appreciate an answer ...
0
votes
2answers
45 views

norms of Symmetric Positive Definite Submatrices

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
2
votes
2answers
49 views

Cholesky Factorization with submatrices

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
1
vote
1answer
182 views

Principal Submatrices of a Positive Definite Matrix

Let $\mathbf{A}\in\mathbb{R}^{N \times N}$ be symmetric positive definite. For some $1\leq k<N$, partition $$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{12}^T ...
1
vote
1answer
73 views

showing condition number of a matrix is the square root of $A^\top A$

For $A \in \mathbb{R}^{m\times n} : m > n, A$ has full rank, I want to show that $k(A^\top A) = k(A)^2$, is there a way to do so purely from $k(A)=norm(A) norm(A^\dagger)$? Recall that $A^\dagger ...
1
vote
0answers
107 views

Using Cholesky factorization to solve the system AXA=B

I have been given a problem of solving X, which is an unblurred image, in the system: $$B = A X A \iff X = A^{-1} B A^{-1}$$ Where the matrix A describes the blurring of an image and the matrix B is ...
2
votes
0answers
47 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...
0
votes
2answers
114 views

Better Gaussian Elimination for solving $Ax=b$ [closed]

We know that Gaussian Elimination is very popular method to resolve $Ax=b$. Does anyone know better method than Gaussian Elimination in term of time complexity? Second question,if I assume that A is ...
0
votes
1answer
55 views

Is $ \frac{ x^T A A x }{ 1+ x^TAx} $ is upperbounded by the biggest eigenvalue of $A$?

I read somewhere that $$ \frac{ x^T A A x }{ 1+ x^TAx} $$ is bounded by the biggest eigenvalue of $A$, where $x \in \mathbb{R}^d$ and $A \in \mathbb{R}^{d \times d}$ and it is PSD. Anyone see why ...
0
votes
0answers
45 views

Finding a function using first derivative

I have some data about just first derivative of a function. Also, I know a point of this function(e.g. (x1,y1)). How can I obtain the function? All my date are numerical. dev f(x)=[ 580.00 , 479.7308 ...
3
votes
1answer
53 views

What is the upper bound on the error of the solution of a noise perturbed linear system $Mx=b$?

Let $x$ be solution to the following linear system: $$ Mx = b$$ and let $ \tilde{x}$ be the solution to the above linear system with some additive noise: $$ M \tilde{x}= \tilde{b}$$ where ...
0
votes
1answer
52 views

Very High degree Polynomial Roots: How to Cope with Large Values?

I hope I'm not duplicating! I'm wondering how it is possible to find all roots of a polynomial of very high degree (100,1000,1000000, ...) numerically. In all numerical methods, the polynomial is ...
3
votes
0answers
120 views

Express Lagrange polynomial in term of Cauchy matrix

Given 2n distinct real numers $s_1,s_2, \dots, s_n$ and $t_1, t_2, \dots,t_n$ define the $n \times n$ Cauchy matrix $C = C(t,s)$ by $C_{ij} = \frac{1}{t_i - s_j}$. Express the Lagrange interpolation ...
2
votes
1answer
46 views

Solving $Ax_2 = \lambda x_1$ and $A^Tx_1 = \lambda x_2$ using SVD

Please using only SVD, I have solved the problem using other methods Solving $Ax_2 = \lambda x_1$ and $A^Tx_1 = \lambda x_2$ using SVD: I am solving this to find $\lambda$ and $x_1,x_2$ To find ...
0
votes
2answers
68 views

Prove that I -xx* is singular if and only x*x = 1

(=>) Suppose I - xx* is singular if and only there is a y such that (I−xx*)y=0, i.e. xx* y=y. Now set λ=x* y. Then y=λx, i.e. xx* λx=λx Thus λx(x* x) = λx => x* x = 1 (<=) Suppose x*x = 1 ...
0
votes
1answer
41 views

Normal Equations error bounds

$A^TAx = A^Tb$ $A^TA\hat{x} = A^Tb + f$ where $\lVert f\rVert \leq cu\lVert A\rVert\lVert b\rVert$ Show that $\frac{\lVert x-\hat{x}\rVert}{\lVert x\rVert} \leq cuK(A)^2\frac{\lVert ...
1
vote
1answer
166 views

Thomas Algorithm for Tridiagonal System

A professor gave us an assignment to solve a Tridiagonal system using Thomas Algorithm. Here is the exercise: I am lost as to what to do with that $(0.2\pi)^2$ and do I just calculate the ...
3
votes
1answer
258 views

Understanding the QR eigenvalue finding algorithm

I'm trying to code up a matrix library (purely as a learning exercise). This question is about the math I'm trying to understand in order to implement it. I just want to make sure I have a firm grasp ...
1
vote
1answer
65 views

Proof of an alternate Matrix Condition Number Representation

I'm currently looking over a section in my textbook on Matrix Condition Numbers and it's given the definition $cond(A) = ||A|| \cdot ||A^{-1}||$ but it's also equated this definition of a condition ...
2
votes
1answer
56 views

Conditioning of Triangular Matrices:

Let $U \in \mathbb{R}^{N\times N}$ be upper triangular. $U$ is well conditioned if the magnitude of the diagonal elements is sufficiently large compared to that of the corresponding off-diagonal ...
0
votes
1answer
84 views

Getting translation and rotation from resultant matrix

I have a matrix which performs a 2D rotation around any given center. Using homogenous coordinates, I have the matrices: $$ T = \begin{pmatrix} 1 & 0 & C_x \\ 0 & 1 & C_y \\ 0 & 0 ...
1
vote
1answer
32 views

Coordinate transformation (or conversion) into yards

Following is a soccer field with its dimensions. There is a similar field, but I am capturing coordinates via mouse-movement. So, what (115,75) shows here, is ...
3
votes
1answer
50 views

prove that $|\lambda(H) - \lambda(B)| \leq \sqrt{||(C^HC)||_2}$

Let A, B be Hermitian square matrices and $$H = \left[\begin{array}{rr}A & C \\ C^H & B\end{array}\right]$$ Show every eigenvalue $\lambda(B)$ of B, there is an eigenvalue $\lambda(H)$ of H ...
0
votes
1answer
26 views

a matrix inverse problem

Given a matrix $X$, let $D$ be a diagonal matrix whose diagonal elements are row sums of $X$, let $I$ be an identity matrix. Now I have a resultant matrix of $Y=(I-X)^{-1}$, and I would like to ...
1
vote
1answer
44 views

Proof that strictly tri-diagonally dominant matrix has an inverse

We are given the following theorem of which we need only know the result. Theorem Suppose an $n\times n$ matrix $A= (a_{ij})$ is tri-diagonal with $a_{i,i-1}a_{i,i+1} \neq 0$, for each ...
1
vote
1answer
101 views

How does one prove the solution of minimum Euclidean Norm to the least squares problem?

If we have some $m \times n$ matrix $A$ with an $m$-vector $b$, how does one prove that the solution $x$ of the minimum Euclidean norm to the least squares problem $Ax \approx b$ is given by $$ x = ...
1
vote
1answer
71 views

convolution and associativity

Ok Let talk about this,... I am now so confused. 1-$$\mathcal{F}\Big\{c(x-x_0)b(x-x_0)\Big\}=\mathcal{F}\Big\{c(x-x_0)\Big\}\circ\mathcal{F}\Big\{b(x-x_0)\Big\}\\=\Bigg[e^{-2ix_0y}C(y) ...