0
votes
0answers
16 views

Modifying U=mxn SVD Algorithm to U=mxm Algorithm

I have painstakingly ported this Python source "svd.py" to C++. I confirm it works for the example it comes with. While testing another example (this one, from Wikipedia), the assert statement trips ...
3
votes
2answers
20 views

Smallest linear combination of a set of vectors

I'm searching for an algorithm to accomplish a (hopefully) simple task. If I have a set of vetors, (e.g. $\left( ...
0
votes
0answers
40 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
0
votes
0answers
24 views

Solving a simple Recurrence in summation form(very special case)

I have a bit confusing recursion form $\sum_{n=2}^{\infty}\{f(n)\frac{n}{n-1}\}=C, \tag 1$ $f(0)=b,f(1)= a,f(2)=c$ and $C$ are constants. Could you help me to solve this recursion or help me to ...
1
vote
0answers
50 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
5
votes
3answers
364 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
7
votes
3answers
228 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
1
vote
1answer
134 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
1
vote
0answers
26 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 & ...
0
votes
0answers
56 views

QR decomposition algorithm

According to G. W. Stewart (Matrix Algorithms: Volume 1, Basic Decompositions) given an $n\times p$ matrix $A$, let $m=\min\{n,p\}$. The Stewart's Householder triangularization algorithm (Chapter 4, ...
2
votes
1answer
48 views

Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
0
votes
1answer
40 views

Find longest vector by summing some vectors in given set

Given $n$ vector $(x_1, y_1), (x_2, y_2),(x_3, y_3),\dots,(x_n,y_n)$. Find a subset S of vector such that $\text{}\left |\sum_{v\in S} v\right |$ Sorry for my English. Please give me a hint how to ...
0
votes
1answer
30 views

Finding end point of straight line given starting point and angle

I have a program which computes the angle of skew of a scanned photograph. It returns the angle of skew in degrees. I now need to draw lines across the image which follow the angle of skew. These ...
1
vote
1answer
11 views

Algorithm to find out on which position ZX is?

I am having the following problem. Lets consider the alphabet. From A-Z there are 26 letters. If its for example AA, then its ...
4
votes
1answer
115 views

Bipartite graph matching like problem.

Let $A=\{a_1,a_2, ..., a_n \}$ and $B=\{b_1,...,b_m\}$ be finite sets. Also $A_1,...,A_k\subset A$ are covering of $A$ and $B_1,...,B_t\subset B$ are covering of $B$. Let $V$ be a set of pairs of ...
3
votes
2answers
78 views

How to extend an existing orthogonal set of vectors?

Suppose I have $k$ vectors in $\mathbb R^n$ that are orthogonal to each other ($k \ll n$). Is there an efficient way to find another vector that is orthogonal to all these given vectors? If we put ...
1
vote
0answers
22 views

Minimize the number of nonzero elements of a matrix through elementary row operations?

Is there a general method to minimize the number of nonzero elements of a real rectangular matrix through elementary row operations? I am looking for something analogous to Gaussian elimination, that ...
2
votes
1answer
78 views

Determining the ratios needed in gear reduction

I am trying to work out the math behind building a gear box for turning a gear a specific RPM from a small motor. Given that a typical DC hobby motor turning at 200 RPM, and a target in the final ...
5
votes
0answers
26 views

Decoding of Gabidulin code

Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
1
vote
1answer
41 views

How to find the size of the largest collection of orthogonal rows

Given a non-square matrix $M$ over the reals, how can you find the size of the largest collection of orthogonal rows?
0
votes
0answers
26 views

Algorithmic Complexity of Linear Independence

Given n m-dimensional vectors. You can determine linear independence by Gaussian elimination. http://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency Checking linear independence ...
1
vote
2answers
56 views

Matrix decomposition definition

Wikipedia says "In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different ...
1
vote
2answers
42 views

Number of solutions for inqeuality

Is there a way we can determine number of solutions for equation $$x*y < d$$ where d is constant and x & y are positive integers greater than 1. I am not interested in actual values, but ...
0
votes
0answers
33 views

Matrix Partial Derivative?? NMF Multiplicative update rules

Recently, I read Lee & Seung's work on Nonnegative Matrix Factorization. But I have problem with the update rule: The object function is minimize: $\|V - MH \|$ with respect to M and H, subject ...
0
votes
0answers
22 views

Iteratively solve linear equations with rank-1 updates on LHS and RHS

What is the best way to iteratively solve updating equations of the form $$ Ax=b $$ $$ (A+c_1v_1^\intercal)x_1=b+ \alpha_1 d_1 $$ $$ (A+c_1v_1^\intercal+c_2v_2^\intercal)x_2=b+\alpha_1d_1+\alpha_2d_2 ...
5
votes
0answers
144 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
4
votes
1answer
45 views

Randomly generate an matrix $A$ s.t. $A^m = I$

Fixed $n$, I want to randomly generate a $n \times n$ real matrix $A$ from the set: $\{A \in \mathcal{M}_{n \times n}(\mathbb{R}): \exists m \in \mathbb{N} \mbox{ s.t. } A^m = I\}$ I think I should ...
1
vote
1answer
35 views

matrix row/col mapping

Many square matrices are symmetric. i.e. $a_{i,j}=a_{j,i}$ For such matrices, we can only store the upper triangle elements, i.e. any $a_{i,j}$ for which $i<=j$. Assume a 10x10 matrix. Using this ...
2
votes
2answers
50 views

Solve linear equation system $A'Ax=A'Bz$

For $A$ and $B$ known matrices which are not square matrices, I have the following equation sistem i would like to solve numerically \begin{equation} A'Ax=A'Bz \end{equation} I want to know which is a ...
2
votes
2answers
100 views

Avoid dividing by zero with just variables and basic operators

I am working on stats for a sports team, and one of the stats I have the ratio of Shots and Shots on Target (Which I call ...
1
vote
1answer
34 views

Fast method to detect if a circulant matrix is singular

I have to write some code to detect if a large number of smallish (less than 20 by 20) square 0-1 matrices are singular over $\mathbb{R}$. As a circulant matrix is defined by its first row and its ...
2
votes
2answers
62 views

Linear Diophantine equation in two variables with additional constraints

Given, $$aX + bY = c$$ where, $$c > b > a > 0;\quad X, Y > 0;\quad b\nmid c, a\nmid c$$ I want to find out if a solution exists as efficiently as possible (I'm not interested ...
0
votes
1answer
69 views

How to tell if there exists a vector orthogonal to half your vectors

Given a set of $N$ vectors each with $n$ entries from the integers. How can you determine efficiently if there is any non-zero vector in $\mathbb{R}^n$ which is orthogonal to half of them?
2
votes
2answers
254 views

Flood algorithm - find polygon containing a given point.

I have some code that represents a set of a set of interconnected line segments in 2D, in pseudo-code it'd be like this: ...
1
vote
1answer
84 views

Solve $Mx = 0$ for $x$

Given an $m$ by $n$ matrix $M$ whose elements are $0$ or $1$, is there an efficient way of finding a vector $x \ne 0$ whose are elements are from $-1,0,1$ such that $Mx = 0$, or even determining if ...
0
votes
0answers
90 views

Strassen's Matrix Multiplication Example Problem

How to multiply two matrices using strassen's matrix multiplication.I have only learned the theory part but i cannot find any examples on the net. Could some one explain with two 2X2 Matrices.
29
votes
6answers
2k views

The milk sharing problem

I found a book with math quizzes. It was my father's when he was young. I encountered a problem with the following quiz. I solved it, but I wonder, is there a faster way to do it? If so, how can I ...
0
votes
0answers
27 views

Levenberg-Marquardt algorithm

Does anyone know if the Levenberg-Marquardt algorithm used to solve non-linear least squares problems has any regularization process?
1
vote
0answers
49 views

Gauss-seidel and implicit method

I have a matrix $\mathbf{X}$ and I want to apply a function $f_{ij}$ to each entry of it, until convergence is satisfied. If a value is known in this matrix, then the $f_{ij}$ at this point may be the ...
3
votes
0answers
659 views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
8
votes
0answers
136 views

Algorithm for obtaining the surface of a mirror

My colleague and I have been trying to implement an algorithm described in the paper "Recovering local shape of a mirror surface from reflection of a regular grid", primary author of which being ...
1
vote
1answer
89 views

Efficient Algorithm for Generalized Sylvester's Equation

Is there an efficient computational algorithm for solving the generalized Sylvester's equation: $\displaystyle \sum_{i=1}^{n}A_{i}XB_{i}=C$ The conventional Kronecker product approach to solve this ...
1
vote
1answer
76 views

Proof for existence of exactly one solution for the number of marbles in each box

There are four boxes A, B, C and D containing marbles. Two boxes are randomly selected and the number of marbles in each box is summarized. This procedure is repeated five times with the ...
0
votes
1answer
70 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
0
votes
0answers
45 views

Operation count for Tridiagonal System

What is the operation count for solving the tridiagonal system $Ax=b$. I would guess it is $O(n^2)$ because all we are doing is making one sub-diagonal zero all the way across giving us $t(n)=n$ and ...
3
votes
0answers
64 views

How to quickly approximate the eigenvectors of a symmetric matrix

Given a symmetric $n \times n$ matrix $A$, is there any algorithm that can quickly approximate all of its eigenvectors? By "quickly", I mean with time complexity less than $\mathcal{O}(n^3)$.
2
votes
0answers
88 views

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
1
vote
2answers
41 views

Solving system of linear eqaution in special cases

I have to solve for $Ax=B$. Here the diagonal elements of $A$ are $-1$ and all other elements are $1$. $A$ is $n \times n$ matrix . In this special case can we solve for $x$ quickly? EDIT: quick is ...
1
vote
1answer
132 views

Computing the number of positive and negative eigenvalues

Given a $n \times n$ symmetric matrix $A$ with integers as entries I would like to compute the number of strictly negative $\rm{nn}(A)$ and positive $\rm{np}(A)$ eigenvalues of $A.$ My question is ...
1
vote
1answer
490 views

Prove Solving a Lower Triangular Matrix By Forward Substitution is Backwards Stable

I'm taking a class in scientific computing and we are working on proving stability of certain algorithms. Unfortunately, at this stage, everything is proof-based, and I have little to no experience in ...