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

learn more… | top users | synonyms

2
votes
1answer
201 views

1D Schrodinger/Laplace equation via finite differences: incompatible eigenvalues

I need to solve a variant of the 1D Schrodinger's equation equation using finite differences, so I decided to play a little bit with the real-space representation of some operators. Using the ...
2
votes
1answer
69 views

Numerical methods for inverting non positive definite matrices

I'm working on a PDE solver and need to invert the following matrix written in block form $\left( \begin{array}{cc} kM & -S \\ -S & M \end{array}\right) $ where M and S are the usual mass and ...
2
votes
1answer
150 views

Question on “avoidance of crossing”

In review of linear algebra I come across this phenomenon, the Google Book link is this: What I do not understand is Lax tried to persuade us that "there is another way of parametrizing these ...
1
vote
1answer
30 views

Recover the inverse after interative solution of a linear system

I have solved the linear system $\mathbf{A} \mathbf{x} = \mathbf{b}$ with an iterative solver. The problem is well-posed ($\mathbf{A}$ is invertible, $\mathbf{b} \ne \mathbf{0}$, blah blah blah). ...
1
vote
1answer
24 views

Is LU decomposition of matrices efficient for today's standards?

This is in the spirit of a previous question of mine about the efficiency of the QR algorithm. The reason for asking is that I want to motivate some students, and I'm also curious. I do understand ...
1
vote
1answer
28 views

A problem about lub and glb of matrix

For any matrix $A\in \mathbb{C}^{n\times n}$, define $$lub_K(A):= \inf\{\alpha\geq 0: AK\subset \alpha K\},$$ and $$glb_K(A):= \sup\{\alpha\geq 0: \alpha K\subset AK\},$$ where $K$ is a equilibrated ...
1
vote
1answer
43 views

Derivative of $\|Ax-b\|_1$

Using least squares approximation $E^2 = \| Ax - b\|^2 = (a_1x - b_1)^2+...+(a_mx-b_m)^2$ The derivative of E^2 at the point $\hat{x}$ is zero if: $(a_1\hat{x}-b_1)a_1+...+(a_m\hat{x}-b_m)a_m=0$ ...
1
vote
1answer
68 views

Solve quadric equation system

How to solve this? For given real and symetric matrices $A_1,A_2,A_3,A_4\in\mathbb{R}^{4\times4}$ find $x\in\mathbb{R}^4$ $$x^TA_1x=0$$ $$x^TA_2x=0$$ $$x^TA_3x=0$$ $$x^TA_4x=0$$
1
vote
1answer
50 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 ...
1
vote
1answer
50 views

Can a tridiagonal matrix be rectangular?

My program works with tridiagonal matrices (calculates its LU decomposition) so before doing anythig, it stores the matrix in 3 vectors: the three diagonals only. So far my conclusion was, a ...
1
vote
1answer
43 views

How to solve an Optimization problem with linear as well as Quadratic constraints.

I want to solve the following problem, \begin{equation} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & \mathbf{x^T}\mathbf{Px} \\ & \text{subject to} & & ...
1
vote
1answer
69 views

Using the Gauss-Seidel method, will the matrix A converge

Just came back from my Numerical Analysis midterm, posting up the questions and my solutions for an estimation as to how I did. If you were to perform the Gauss-Seidel method on a matrix $A$, where ...
1
vote
1answer
109 views

Partial QR factorization to solve least squares problem

I'm trying to understand how to solve a least squares problem of the form: $$\begin{bmatrix}A& B \end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = [b]$$ where I only explicitly solve for $y$ and ...
1
vote
1answer
146 views

Minimizing the Determinant

I would like to minimize the determinant of the following matrix, det(A) $A = (VV^T+\lambda I)^{-1}$ and $\lambda$ is set to be very small.
1
vote
1answer
129 views

Solving Poisson Equation Finite-difference using maple

How do I solving Poisson Equation Finite-difference using maple consider Poisson equation $$\frac{\partial^2u}{\partial x^2} (x,y)+ \frac{\partial^2u}{\partial y^2} (x,y) = x*e^y$$ $0<x<2$ ...
1
vote
1answer
156 views

Numerical range of a matrix contains the convex hull of the eigenvalues.

I am stuck with the following question. Question: Let $A \in \mathbb{C}^{m \times m}$ be arbitrary. Let $W(A)$ be the numerical range i.e. the set of all Rayleigh quotients of $A$ corresponding to a ...
1
vote
1answer
57 views

Prefactoring to solve many similar linear systems

I am designing an algorithm that needs to solve many (large) linear systems of the form $$\Phi^\top D_i\Phi \vec x_i=\vec r_i,$$ where $\Phi\in\mathbb{R}^{m\times n}$ with $m>n$ is fixed. We will ...
1
vote
1answer
52 views

What is the range of this function

Let $\lambda_{1}(X)$ be the larger eigenvalue of the $2$ eigenvalues of a symmetric matrix X. For fixed real numbers $a,b,c,d$, what is the range of $\lambda_{1}\left(diag\left(a,b\right)-U\cdot ...
1
vote
1answer
494 views

How to find the Householder transformation?

Assume $x=(1,0,4,6,3,4)^T$. Find a Householder transformation and a positive number $\alpha$ such that $Hx=(1,\alpha,4,6,0,0)^T$. I'm sorry that I don't know how to start with this problem. A ...
1
vote
1answer
111 views

Eigenvalues of discretized linear integral operator

Suppose I have the following kernel operator: $Af(x) = \int_{-1}^1 K(x-y)f(y)dy$ which is also positive and compact. Hence, it has a countable set of positive eigenvalues. Suppose those eigenvalues ...
1
vote
1answer
181 views

Limiting Degrees of Freedom in 3D Point Registration

I'm search for some assistance in my application of Arun's algorithm for registration (fitting) of two 3D point sets using the Singular Value Decomposition: ...
1
vote
1answer
61 views

Help regarding a weird Matrix

Hi I have a matrix of the following form arising by discretization of a system of PDEs. I am working to get the invertibility of the Matrix. Can some one help me or at least give me some reference on ...
0
votes
1answer
3 views

Inversing badly-conditioned square matrix: methodology

I have a badly-conditioned square matrix. I need to inverse it. For inversing, currently I'm doing the following steps: I take the badly-conditioned matrix with size of $n$ by $n$ By reduced row ...
0
votes
1answer
30 views

Norm of Outer Product

Let $x \in \mathbb{R}^N$ and $ y\in \mathbb{R}^M$. Show that $\|xy^T\|_{\infty}=\|x\|_{\infty}\>\|y\|_1$ I've been able to show the following: $\|xy^T\|_{\infty}= \|xIy^T\|_{\infty} \le ...
0
votes
1answer
32 views

Heat equation in 1D with collocation method

I want to use the collocation method to solve $u_t=u_{xx}$. I impose the PDE pointwise and expand the solution in Fourier Series: $$ \partial_{t}\sum_{k=-K}^{K}\hat{u}_{k}(t)\ ...
0
votes
1answer
63 views

subtraction between sum of all elements of two symmetric matrices

Let assume that I have an $n\times n$ symmetric matrix $A$ and I know $A^{-1}$. Now, I have a new matrix $$M = \begin{pmatrix} A & b \\ b^T & c \end{pmatrix},$$ where $b$ is a vector and ...
0
votes
1answer
49 views

Why won't my conjugate gradient algorithm work?

I made this simple Conjugate Algorithm on Matlab n = length(b); r0 = b - A*x0; p0=r0; k=1; n0=(r0')*r0; while n0 >= eps && k <= n ...
0
votes
1answer
30 views

convolution on 2 by 2 matrices

Let $m$ be a positive integer, and let $A_1,B_1 \in \operatorname{SL}(2,\mathbb{Z})$. Can one always find matrices $A_2,B_2 \in \operatorname{SL}(2,\mathbb{Z})$ such that $$ A_1 \left( ...
0
votes
1answer
50 views

How does the Simplex method of solving LPs use the starting solution?

Say one looks at the LP (in slack form) and sees that assigning $0$s to all the non-basic variables doesn't give a valid solution but some other non-trivial assignment of values to the non-basic ...
0
votes
1answer
78 views

Solve Bratu problem using Python

I am going crazy trying to solve the Bratu problem using Python: $$y''(x)+ e^{y(x)} = 0, \quad \lambda = 1, \quad x \in(0,1),$$ $$y(0) = y(1) = 0$$ I have to solve this using the tridiagonal ...
0
votes
1answer
34 views

What is the computational cost of reduced row echelon and finding the null space?

I'm taking computational linear algebra, and haven't been able to find too much information about the computational cost (in terms of m=rows and n=cols) of these two routines: Reduced Row Echelon ...
0
votes
1answer
81 views

How do I find transformation matrix with respect to given basis in the domain and/or the codomain, given the transformation in the standard basis?

I´m being given a linear transformation, for which I can find the standard basis in the domain and codomain; but then, the book ask to find the associated matrix related to a new basis for the ...
0
votes
1answer
46 views

An algorithm of solving a non-homogeneous linear equation by random matrices

I'm looking for the proof of the following numerical algorithm. Suppose I want to solve a non-homogeneous linear equation \begin{equation} A x = b \end{equation} The matrix $A$ is non-invertible and ...
0
votes
1answer
25 views

Function from one Null space to Another

Suppose a single vector space over $R$ of degree $n$, and two matrices $A, B$ of arbitrary row size, but col size $n$, s.t. their individual null spaces are linear subspaces of this vector space. Is ...
0
votes
1answer
73 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
0
votes
1answer
63 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
1answer
117 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
1answer
66 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 $\odot$ ...
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
1answer
32 views

Using Givens Rotation on a vector

Say we have a vector v=$[3\ 0\ 4]$. Find a 3x3 orthogonal matrix Q such that only the second component of Qv is nonzero and such that this component is also positive. Is Q unique? I tried ...
0
votes
1answer
59 views

Show that the iteration $x_{n+1} = x_n - 2\frac{f(x_n)}{f'(x_n)}$ converges quadratically to $x_*$ provided $x_0$ is sufficiently close to $x_*$

We have the following conditions for the above slightly-modified Newton's method iteration: $f$ is a real function of one real variable $f''$ is Lipschitz continuous $f(x_*) = f'(x_*) = 0$ I also ...
0
votes
1answer
51 views

Numerical Linear Agebra

how to Prove the backward stability of the inner product ? ...
0
votes
1answer
62 views

Householder Reflection

I am working on algorithms for SVD by first performing Householder transformation. I got my algorithm to work but I'm trying to gain a better intuition of it. My understanding is that the ...
0
votes
1answer
41 views

Is it possible to solve a system of equations comprising FFTs?

Consider the following known matrices, A, B, C and these unknown matrices X,Y, all of which comprise values in the Real domain. Also consider $F(x)$ as the *Fast Fourier Transform function* (the ...
0
votes
1answer
80 views

Inverse Square root of a rectangular matrix

I am trying to compute the inverse square root ($X^{-1/2}$) of a $n \times p$ matrix with $n > p$. I was wondering if we can compute it via SVD just as we do it for square diagonalizable matrices ...
0
votes
1answer
30 views

Residual norm for iterative scheme

Consider a linear system $A\vec{x} = \vec{b}$, where $A \in \mathbb{R}^{m\times{}m}$ is non-singular and positive definite. Given the following iteration scheme $\vec{x}^{(k+1)} = \vec{x}^{(k)} + ...
0
votes
1answer
62 views

Can a 6-arm star be convex

Please help me with the following question. Suppose that the constant level contours of some function $V:\mathbb{R}^{2} \rightarrow \mathbb{R}$ have the shape of a symmetric 6-arm star. Can such a ...
0
votes
1answer
82 views

Fast Gauss-Seidel convergence on low rank matrices

I stumbled upon the following remarkable fact when experimenting with the Gauss-Seidel iterative solver: First I construct a low-rank symmetric positive semi-definite matrix $A = M^TM$ with M a ...
0
votes
1answer
89 views

Completeness of eigenvectors of Hermitian Matrix.

How do you show that eigenvectors of a Hermitian matrix form a complete set of basis?
0
votes
1answer
17 views

Are Similar Matrices and Unitary Property related?

Recall that 2 matrices $A, B\in R^{n,n}$ are similar if there exists a matrix $P$ such that $A=P^{-1}BP$. In this case is $P$ always orthogonal?