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

learn more… | top users | synonyms

1
vote
2answers
472 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
2answers
75 views

eigenvalues for symmetric and non-symmetric matrices

I know the Power methods and Jacobi methods are suitable to finding eigenvalues for symmetric matrices, please tell me other methods for this matrices. And what are the methods for the Non-symmetric ...
1
vote
2answers
234 views

Space spanned by matrices

I have a set of 5 by 5 matrices, M1,M2,...,M19 ,M20. I want to try to find a basis from this set and also to find relationships between these matrices. This is how I think I should approach the ...
0
votes
2answers
100 views

Different method for QR decomposition - is it possible

This method could also possibly be applicable to matrices of higher dimension, but for the simplicity of my question i will only ask it for $2$x$2$matrices. Suppose $A=\begin{pmatrix} a_{11} & ...
0
votes
2answers
48 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
2answers
34 views

Minimum of Maximum of Addition of two vectors/arrays

Suppose you have two arrays and you want to compute the maximum of the addition of the two arrays. Now you move the second array one field to the right. Now you can compute the maximum again of the ...
0
votes
2answers
405 views

determine whether the equation $Ax = b$ is consistent for every $b$ in $\mathbb R^m$

I have two problems, the first one is the following matrix: $$\begin{bmatrix}1 & 0\\ -2 & 1\end{bmatrix}$$ where the RREF is $$\begin{bmatrix}1&0\\0&1\end{bmatrix}$$ and where the ...
0
votes
2answers
57 views

How to understand or show this?

We have $$F=ABh^{p_1}+\theta (h^{p_2})$$ $$G=Ah^{p_1}+\theta (h^{p_2})$$ We $A$,$B$ are real numbers, $h$ positive, $|h|\leq 1$ , $p_1<p_2$ natural numbers and $\theta(h)$ means that it is of ...
0
votes
2answers
38 views

Efficiently updating a vector

What is the most efficient way to make this linear algebra computation? I am interested in computing a vector $y^{(k)}$ that updates as shown below. $$y^{(k)} = A^k B A^k x$$ where the matrices $A,B ...
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
478 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
107 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
177 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
60 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
23 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
43 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
73 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
28 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
65 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
42 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
70 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
57 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
87 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
56 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
58 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
50 views

Numerical Linear Agebra

how to Prove the backward stability of the inner product ? ...
0
votes
1answer
57 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
38 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
73 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
29 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
61 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
79 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
81 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
62 views

Rate of Convergence of Generalized Iterative Method

Consider the generalized iterative method for finding polynomial roots: $z_{k+1}=z_k +d\frac{(1/p)^{(d-1)}(z_k)}{(1/p)^{(d)}(z_k)}$ where d is a positive integer. Note that Newton's Method is a ...
0
votes
1answer
115 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$ ...
0
votes
1answer
16 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?
0
votes
1answer
27 views

Set up for matrix solutions

I've haven't touched linear algebra in a while so I'm sorry if this seems simple but I did a google search and I am still confused. I have to find a solution to the following set of equations: ...
0
votes
1answer
282 views

If $(V,k)$ is a finite-dimensional vector space, then the space of all linear transformations on $V$ is finite dim and find its dim?

My issue with this is the only way I know how to prove it is to set $\dim V=n$, but then that wouldn't make sense because the second part is find the $\dim$. What I was thinking is using the ...
0
votes
1answer
86 views

matrix positive semidefinite

If $n \times n $ matrices $A, B$ are positive semi-definite, matrices $P$ and $Q$ are $n\times p$ and $n\times q$ matrices and their column vectors are orthogonal, which is to say $$P^{T}P=I_{p\times ...
0
votes
1answer
44 views

Simple question about equivalence of two forms of PCA as trace maximization over an implicit distribution

This may be a soft question of sorts. One formulation of principal component analysis is trace maximization: $$\arg\max_U \mathbb{E}_x \ [tr(U^Txx^TU)],$$ for $U^TU\le I$ and we assume that there is ...
0
votes
1answer
25 views

Given an M x N matrix, is there a way to produce an orthogonal set of N vectors of length M, where M < N?

Gram-Schmidt orthogonalization would only use the first M vectors to generate a basis of size M x M.
0
votes
1answer
69 views

Matrix existence..

How to prove that for any matrix $A\in \mathbb R^{m\times n}$ ($m\geq n$) such that $rank(A)=r$ there exists a nonsingular matrix $P$ and an orthogonal matrix $U$ such that, \begin{align*} A=U\Gamma ...
0
votes
1answer
120 views

Numerical linear algebra (pseudoinverse of a matrix)

Let $A$ be the matrix: $$\left(\begin{matrix} \alpha I_{n} \\ \beta I_{n} \end{matrix}\right)$$ where $\alpha,\beta\in\Bbb C$ are not both zero. Derive (a) the (reduced) QR factorization of $A$ ...
0
votes
1answer
77 views

relative error relation

Let $x$ be a non-null quantity. Let $\hat{x}$ be its approximation. I am trying to find the relation between: $\frac{\left | x-\hat{x} \right |}{\left | x \right |}$ and $ \frac{\left | x-\hat{x} ...
0
votes
1answer
90 views

Iterative Method for a special kind of Sparse Matrix

I've the following problem.I've a sparse square Matrix $\bf M$. I can write $\bf M$ as: $${\mathbf M} = \begin{bmatrix}\mathbf A_{11} & \dots & \mathbf A_{1n} \\ \vdots & \ddots & ...
-1
votes
1answer
216 views

Positive linear combination of vectors to produce a positive vector

Given a list of vectors, I want a linear combination with positive coefficients that produces a final vector with only positive values (EDIT: this final vector is unknown; any positive vector is ...