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

learn more… | top users | synonyms

2
votes
1answer
112 views

SOR and Gauss-Seidel Method - Confusion

Can anyone explain to me the SOR Method for finding the root(s) of a function? Its supposedly very similar to the Gauss-Seidel method. The Gauss-Seidel method, from my understanding, is similar to ...
1
vote
2answers
148 views

Householder QR Factorization for m by n Matrix (both m>=n and m<n)

Why in all of books I read about numerical linear algebra (e.g. Matrix Computations by Golub and Numerical Linear Algebra and Applications by Datta and many others), Householder QR factorization have ...
3
votes
3answers
314 views

What is the practical impact of a matrix's condition number?

Let's say I am trying to solve a square linear system $Ax = b$ for whatever reason. A perturbation $\delta b$ in $b$ will lead to a perturbation $\delta x$ in $x$, whose relative norm is bounded by ...
0
votes
1answer
32 views

Is the scheme for generating $\displaystyle p_n=\left(\frac{1}{3}\right)^n$ stable? [duplicate]

Is the scheme for generating $\displaystyle p_n=\left(\frac{1}{3}\right)^n$ stable? $\displaystyle p_{n} = \frac{5}{6} p_{n-1} - \frac{1}{6} p_{n-2}$
0
votes
0answers
17 views

Singularity check for Homographies

I know that the standard singularity check for a matrix represented in some finite-precision format (IEEE-754 or whatnot) is "the matrix is singular if the reciprocal of the condition number of the ...
0
votes
1answer
184 views

Linear Transformation induced by the following matrix A

Suppose $T:\mathbb R^4\rightarrow\mathbb R^4$ is the transformation induced by the following matrix $A$. Determine whether $T$ is one-to-one and/or onto. If it is not one-to-one, show this by ...
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 ...
0
votes
2answers
38 views

Stability of method through step size

When investigating the stability of a system of ODEs,$$u'=Au$$ where $A$ is diagonalisable so $$u'=R\Lambda R^{-1}u.$$ then let $y(t)=R^{-1}u(t)$ such that $$y'=\Lambda y.$$ Let ...
1
vote
1answer
44 views

Algorithm to generate normal matrices at random

I would like to generate normal matrices by an, say python, algorithm, that produces normal matrices distributed evenly in the limit of large n. I would not like to be restricted to Hermitian matrices ...
2
votes
1answer
46 views

Orthogonality on complex inner product space

Let $V$ be a complex inner product space. I need to show the following: $(x\ and \ y\ are\ orthogonal)\ \Rightarrow (\left \| \lambda x+\beta y \right \|^{2}=\left | \lambda \right |^{2}\left \| x ...
0
votes
0answers
18 views

Is any method which allows segmentation of long diagonalizing procedures?

This is a question for a smarter way of numerical computation. When I diagonalize a certain type of Vandermonde-matrices in Pari/GP ("mateigen(M)"), for instance of size 16x16 then this can be ...
0
votes
1answer
41 views

For which $a \in \mathbb{R}$ Jacobi converge?

I tried to solve the following problem and I don't know if it's correct and I have a few questions: Let \begin{align} A = \left[ {\begin{array}{cc} a & 1 & 0 \\ 1 & a & 1 \\ 0 & ...
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
64 views

Stability analysis of Numerical Method

For a system of ODEs, I'm looking at the case where $$u'=Au$$ where $A$ is diagonalisable so $$u'=R\Lambda R^{-1}u.$$ In the notes I am looking at it goes on to say we can premultiply by $R^{-1}$ so ...
0
votes
0answers
55 views

(Numerical) Cholesky Decomposition of a Product of Matrices

Let $E$ be a symmetric positive definite matrix and let $O$ be an orthonormal matrix i.e. $O^{T}O=I$. Let $chol(A)=L$ such that $A=LL^{T}$ i.e. $chol(.)$ is the operation that returns the lower ...
1
vote
1answer
109 views

Does a Convex Function need to be Continuous

I have been trying the following problem and I am very confused. If possible the problem should be solved with derivatives. If the derivative exists for all the points on the graph then it is ...
0
votes
2answers
274 views

Quadratic Function must be positive definite to have a unique minimum

I have attempted the following question multiple times and I am very confused about the proof please help me solve it. Let $V(x)=a+b^{T}x+\frac{1}{2}x^{T}Cx$ for some $a \in \mathbb{R}, b \in ...
2
votes
2answers
310 views

Power iteration sign of eigenvalue?

I need to write a program which computes all eigenvalues and corresponding eigenvectors. I'd like to use power iterations method (I know that it's not good but it's really necessary). my algorithm ...
0
votes
1answer
62 views

spectral radius of matrix with elements less than one

Assume we have a square matrix A whose elemnts are less than 1, Can we say that its spectral radius is also less than 1. Can we say that the absolute value of its eigenvalues are also less than 1?
3
votes
3answers
157 views

Demonstrate that a matrix has no LU factorization

Have to show that $$\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}$$ has no LU factorization. It seems trivial just to say that this cannot have an LU decomposition because it is a lower ...
0
votes
0answers
57 views

what is the meaning/characteristics of the component-wise product of right and left eigenvectors.

I have a generic, but seemingly simple question : what is the meaning/characteristics of the component-wise product of right and left eigenvectors (for the same eigenvalue of course) ? let's call ...
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 ...
0
votes
1answer
74 views

Impossible Schur Factorizations

I am having trouble finding the schur factorization of the following matrix: $A=\begin{pmatrix}3&8 \\ -2&3 \end{pmatrix}$ I followed an algorithm in the book, as well as computing an answer ...
0
votes
0answers
56 views

Tridiagonal Gaussian Elimination: Band Storage

I was given this algorithm for Tridiagonal Gaussian Elimination: Band Storage for i = 2:N if W(3,i-1) is zero error('the matrix is singular or pivoting is required') end m = W(4,i)/W(3,i-1) ...
1
vote
1answer
145 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.
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 ...
3
votes
1answer
85 views

Prove this matrix is invertible for $n < m-1$

Prove this $(n+1)\times (n+1)$ matrix $\bf{A}$ is invertible for $n < m-1$ and the $x_k$ distinct, \begin{bmatrix} m &\sum_{k=1}^mx_k &\sum_{k=1}^mx_k^2 &\cdots ...
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?
1
vote
1answer
86 views

condition number after scaling matrix

Maybe a well-known question. Let $\Sigma$ represent a real symmetric positive definite matrix, i.e. a covariance matrix. Which diagonal matrix $D$ with positive diagonal minimizes the condition ...
0
votes
0answers
51 views

Least squares problem where rows are multiplied by a factor

I want to solve the following linear system in least squares sense: $Ax = b$ Where $A$ is a sparse matrix which has more rows than columns. To solve it in least squares sense I would need to solve ...
0
votes
1answer
27 views

Proving the equality: $D^{-1}+D^{-1}CPBD^{-1}=(D-CA^{-1}B)^{-1}$ where $P=(A-BD^{-1}C)^{-1}$

I am trying to prove the following equality that I need to use as an intermediate step to solve one of my problems. The equality is the following: $D^{-1}+D^{-1}CPBD^{-1}=(D-CA^{-1}B)^{-1}$, where ...
0
votes
1answer
75 views

Dense symmetric positive definite matrix

How could one define a dense symmetric positive definite matrix (dimension $1000 \times 1000$) with uniformly distributed eigenvalues (with the smallest eigenvalue $1$ and the condition number $100$) ...
2
votes
0answers
47 views

linear algebra formulation help

I asked this on mathoverflow as well and apologies for cross-posting. I am trying to compute this so-called bending energy matrix. The bending energy of a thin plate in 3D is given by: $$ BE = ...
2
votes
1answer
154 views

Help in this exercise about Richardson extrapolation.

We know $F(h)=a_0 +a_1h + a_2 h^3$ $F(1)=4$; $F(1/2)=21/8$; $F(1/4)=145/64$ Find a approximation of $F(0)=a_0$ with Richardson extrapolation method with an absolute error less than $10^{-2}.$ ...
0
votes
1answer
28 views

If $λ_i > 0, \forall i$, $A$ is positive definite

Given that $A \in R^{n,n}$, $λ_i $ the eigenvalues and $x_i$ the eigenvectors ($x_i^Tx_j=δ_{ij}$). I have to show that if $λ_i > 0, \forall i$, $A$ is positive definite. My idea is the following: ...
1
vote
0answers
113 views

Proof-finding: Power iteration and complexity of the Rayleigh quotient

I'm searching for a proof for this theorem: \begin{align} |\lambda^{(k)}-\lambda_1| = \mathcal{O}\Big(\Big|\frac{\lambda_2}{\lambda_1}\Big|^{2k}\Big) \end{align} where \begin{align} \lambda^{(k)} ...
4
votes
4answers
401 views

How to find 2x2 matrix with non zero elements and repeated eigenvalues?

I need to find a 2x2 matrix with non zero elements that has eigenvalue = 1 repeated (double). How can i do that? Thanks!
1
vote
1answer
109 views

Computing the best-fit plane normal from n points

I've been working steadily through "3D Math Primer for Graphics and Game Development" and am stuck on how the authors derived their equation for the best-fit plane normal given n points. Please note, ...
3
votes
0answers
101 views

Difference between Householder Reflections and Gram-Schmidt?

In numerical QR decomposition, when we calculate the orthonormal factor Q of a matrix, what is the difference in results if we use Householder Reflections to normalize the matrix or use Gram-Schmidt ...
1
vote
2answers
51 views

Can you compute rank r factorization of a n*n matrix in time O(n^2 r)?

I am wondering if you can compute the SVD/eigenvectors of a rank r matrix of size n*n in time O(n^2 r)? My understanding is that standard eigenvector computations involve bringing matrix into ...
0
votes
0answers
153 views

Solve system of equations AXB = 0

Is there a common approach to solve a system of linear equations in a form $A^TXB = \bf{0}$? Where $A$ and $B$ are known matrices and $X$ is an unknown matrix. This seems simple enough, there should ...
0
votes
2answers
58 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
1answer
63 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 ...
2
votes
3answers
105 views

properties of positive definite matrix

If $A$ is a symmetric positive definite matrix can we conclude $A^{n}$ is positive define too? Why? For example for $n=2$: $x^{T}(AA)x=x^{T}(AA^{T})x=(x^{T}A)^2>0$; for $n>2$?
0
votes
1answer
43 views

function of matrix and eigen values

I want to calculate exp(A), A is matrix, with numann series. is this series depend of matrix's eigen values? for example if it's eigen values are large, is numann series useful for this function?
0
votes
1answer
77 views

Differences between methods for solving linear equation system

I have a huge linear equation system in this form: F=K.Δ as usual form of problems in the finite element method, where the F vector and K are known and Δ vector is unknown. There are several ...
1
vote
1answer
183 views

Need matlab help to construct a numerical example for solving system of linear equation for random matrices

I am reading this paper(page 183). In this paper the iterative methods for computing some solution of the general restricted linear equations \begin{eqnarray} Ax = b, ~~~~ x\in R(A^{k})~~~~ b\in ...
1
vote
1answer
56 views

most efficient way to find distinct complimenting subspaces over a finite field

Let $V$ be a $n$-dimensional vector spaoce over $\mathbb{F}_p$ and let $W$ be a $k$-dimensional subspace. What's the most efficient way to algorithmically write down a basis for each distinct ...
3
votes
1answer
88 views

Understanding higher order SVD

Can someone explain the singular value decomposition of a tensor (maybe a 3 dimensional matrix) with an example? It is intuitively difficult to the get the meaning from just the formulas. On a ...
0
votes
2answers
63 views

A linear programming to obtain “canonical basis of convex cone”

In my research a I need to solve the linear equation (getting its null space) under some constraints. The matrix is given below: The constraints shall be (x1...x[16]>0, x[17]...x[20] arbitary...) ...